「CCO 2020」购物计划

Posted on Edited on In

「CCO 2020」购物计划

核心思想：堆+调整临近

\(x_i=y_i=1\)

这个限制相当于每一组内的权值排名可以确定，设组内为 \(A_{i,j}(j\ge 1)\)

那么我们一个方案的选择可以用 \(M\) 个指针 \(P_i\) 表示，和为 \(\displaystyle \sum A_{i,P_i}\)

考虑用调整的方式解决这个问题，大体思路上，我们可以记录当前移动指针 \(P_p\)

每次可以选择移动 \(P_p\) ，或者某一个 \(P_{i},i>p\)

如果直接进行，每次移动的指针数量是 \(O(m)\) 级别的，显然不可行

考虑优化一下进行，每次只能选取 \(i=p+1\)

此时，编号小的会先被移动

为了保证答案单调性，我们需要将 \(A_{i,2}-A_{i,1}\) 较小的组先移动

同时，并不是每一个组都会被移动，因此转移还要支持一个特殊回撤操作，来撤回当前组的指针

也就是说，若 \(P_p=2\) ，可以选择把 \(P_p\) 回撤为 \(1\) ，然后将 \(P_{p+1}\) 改为 \(2\)

由此，每个点状态可以选择：

1.移动自己

2.移动下一个

3.若 \(P_p=2\) ，回撤自己，同时移动下一个

这样的调整法，可以保证每一个状态恰好有一个前驱，且转移过程中值不断变大

由此可以 \(O(k)\) 状态数进行调整，用堆维护，复杂度为 \(O(k\log k)\)

\[ \ \]

组内调整

一个组内会选择若干个数 \(A_{b_i},i\in [1,c]\)

初始最小值，显然满足 \(b_i=i\)

类似的，我们记录当前指针 \(p\) ，前驱指针 \(l\) ，后继指针 \(r\)

显然 \(p\) 要往后移，且不能达到 \(r\) ，因此决策只有两种

1.移动前驱 \(l\) ，并将当前指针变为前驱

2.移动自己 \(p\)

这样的调整是固定个数的，因此，一开始就把 \(c\in[x_i,y_i]\) 的所有情况插入即可

\[ \ \]

最后，将两部分一同进行，每次组间调整时，通过组内调整查询答案

总的组内和组间调整次数均为 \(O(k)\) ，状态数分别不超过 \(2k,3k\)

复杂度为 \(O(k\log k)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
char IO;
int rd(){
    int s=0;
    while(!isdigit(IO=getchar()));
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return s;
}
enum{N=200010,LINF=1ll<<60};

int n,m,k,I[N]; ll L;
struct Group{
    vector <int> A;
    int l,r,c;
    struct Node{
        int l,p,r; ll s;
        bool operator < (const Node &__) const { return s>__.s; }
    };
    priority_queue <Node> que;
    vector <ll> V;
    void Init(){
        l=rd(),r=rd(),sort(A.begin(),A.end()),c=A.size();
        if(c<l) {
            rep(i,1,k) puts("-1");
            exit(0);
        }
        r=min(r,c);
        rep(i,0,l-1) L+=A[i];
        ll s=0;
        if(!l) V.pb(0);
        rep(i,0,c-1) {
            if(i>=r) break;
            s+=A[i];
            if(i>=l-1) que.push((Node){i-1,i,c-1,s});
        }
    }
    void Next(){
        if(que.empty()) return V.pb(LINF);
        Node t=que.top(); que.pop();
        V.pb(t.s);
        if(t.p<t.r) que.push((Node){t.l,t.p+1,t.r,t.s-A[t.p]+A[t.p+1]}); // Move current point
        if(~t.l && t.l<t.p-1) que.push((Node){t.l-1,t.l+1,t.p-1,t.s-A[t.l]+A[t.l+1]}); // Move previous point 
    }
    // get kth sum
    ll operator [] (const int &k){
        while((int)V.size()<k) Next();
        return V[k-1];
    }
} S[N];

struct Node{
    int x,y; ll s;
    bool operator < (const Node &__) const { return s>__.s; }
};
priority_queue <Node> que;

int main(){
    n=rd(),m=rd(),k=rd();
    rep(i,1,n) { int x=rd(); S[x].A.pb(rd()); }
    rep(i,1,m) S[i].Init();
    printf("%lld\n",L),k--;
    rep(i,1,m) I[i]=i;
    sort(I+1,I+m+1,[&](int x,int y){ return S[x][2]-S[x][1]<S[y][2]-S[y][1]; });
    que.push((Node){1,2,L-S[I[1]][1]+S[I[1]][2]});
    while(k) {
        Node t=que.top(); que.pop();
        if(t.s>=LINF) break;
        k--,printf("%lld\n",t.s);
        int i=I[t.x],j=I[t.x+1];
        que.push((Node){t.x,t.y+1,t.s-S[i][t.y]+S[i][t.y+1]});// Move current point
        if(j) que.push((Node){t.x+1,2,t.s-S[j][1]+S[j][2]}); // Move next point
        if(t.y==2 && j) que.push((Node){t.x+1,2,t.s-S[i][2]+S[i][1]-S[j][1]+S[j][2]}); 
        // Back current point ,and move next point
    }
    while(k--) puts("-1");
}