「NOI2019」序列

发表于 更新于 分类于

题目链接：https://loj.ac/problem/3158。

一开始写假了重构了一遍代码，我太难了QAQ

有一个比较好想的费用流模型，首先限制可以改为一对一对的选，一共只能选$k-L$对不相同的下标。

那么左右两排点，显然先对应连，然后建$a,b$两个辅助点，$a\to b$容量$k-L$费用$0$，$a_i\to a,b\to b_i$容量$1$费用$0$，这样就能满足限制了。

我一开始写的假算法就是说直接模拟这个费用流，但是好像不太行，有一种增广路我不会维护。。。

换种思路，想想这个增广的过程，会发现一旦选了两个下标，以后永远也不会撤销这一步，并且这个费用流每次都是选能选的和最大的两个。

那么直接贪心，维护几个堆就好了。

复杂度$O(n\log n)$。

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<bits/stdc++.h>
using namespace std;

#define int long long 

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;

#define hp priority_queue<pii > 

int n,k,l,a[maxn],b[maxn],r,ans,v1[maxn],v2[maxn];

hp s1,s2,s3,s4,s5;

int ep(hp &x) {return !x.empty();}
int tp(hp &x) {return x.top().fr;}
int wh(hp &x) {return x.top().sc;}

void cl(hp &x) {
    while(ep(x)) x.pop();
}

void solve() {
    read(n),read(k),read(l);r=k-l;r<<=1;
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=n;i++) {
        read(b[i]),s1.push(mp(a[i]+b[i],i));
        s2.push(mp(a[i],i));
        s3.push(mp(b[i],i));
    }
    for(int i=1;i<=k;i++) {
        while(ep(s1)&&(v1[wh(s1)]||v2[wh(s1)])) s1.pop();
        while(ep(s2)&&(v1[wh(s2)]||v2[wh(s2)])) s2.pop();
        while(ep(s3)&&(v1[wh(s3)]||v2[wh(s3)])) s3.pop();
        
        while(ep(s4)&&v2[wh(s4)]) s4.pop();
        while(ep(s5)&&v1[wh(s5)]) s5.pop();

        int x=0,y=0,z=0,p=0,q=0;
        if(ep(s1)) x=tp(s1);
        if(ep(s4)&&ep(s2)) y=tp(s4)+tp(s2);
        if(ep(s5)&&ep(s3)) z=tp(s5)+tp(s3);
        if(ep(s4)&&ep(s5)) p=tp(s4)+tp(s5);
        if(ep(s2)&&ep(s3)&&r>=2) q=tp(s2)+tp(s3);
        ans+=max(max(x,y),max(z,max(p,q)));

        if(x>=y&&x>=z&&x>=p&&x>=q) {
            x=wh(s1),y=x;s1.pop();
        } else if(y>=z&&y>=p&&y>=q) {
            x=wh(s2),y=wh(s4);s4.pop(),s2.pop();
            s4.push(mp(b[x],x));
        } else if(z>=p&&z>=q) {
            x=wh(s5),y=wh(s3);s5.pop(),s3.pop();
            s5.push(mp(a[y],y));
        } else if(p>=q) {
            x=wh(s5),y=wh(s4);s4.pop(),s5.pop();r+=2;
        } else {
            x=wh(s2),y=wh(s3);r-=2;
            s4.push(mp(b[x],x)),s5.push(mp(a[y],y));
        }
        v1[x]=v2[y]=1;
    }
    write(ans);
}

void clear() {
    cl(s1),cl(s2),cl(s3),cl(s4),cl(s5);
    for(int i=1;i<=n;i++) v1[i]=v2[i]=0;ans=0;
}

signed main() {
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    
    int t;read(t);while(t--) solve(),clear();
    return 0;
}