CF1257E The Contest

一道锻炼前缀、后缀、差分、化式子能力的好题

题意：

给你三个集合A,B,C，集合大小分别为an，bn，cn，且an+bn+cn=n

满足三个集合的并集正好是整数1~n

每次操作可以将一个任意集合中的任意数字扔到另一个集合中

问至少需要几次操作使得每个集合内的数字都是连贯的（空集也可以，且A中所有元素小于B中所有元素，B中所有元素小于C中所有元素

题解：

为了满足题目要求，不妨假设A中含0到i，B中含i+1到j，C中含j+1到n+1（0和n+1是不存在的）

显然的，此时答案ans就是每个集合中不属于自己的元素的个数和

设a[i]表示A集合中含有数1~i的个数，b[i]与c[i]同理

利用差分的思想可以得出此时要扔进这三个集合的元素个数分别为$(b[i]+c[i])$，$(a[j]-a[i]+c[j]-c[i])$，$(a[n]-a[j]+b[n]-b[j])$

加起来就得到

移项

抵消

发现上面这个式子已经可以$O(n^2)$得出答案了，但是不够，我们继续化简

注意到j的取值范围一端（后半部分）是固定的，这意味着可以使用后缀最小值

设$mi[i]=\min \left \{ c[j]-b[j]|i<=j<=n \right \} $

也就是$mi[i]=\min \left \{ c[i]-b[i],mi[i+1] \right \}$

代入原式，最终得到：

一维的式子已经得到，但还要注意对于空集的处理

即枚举i时都要把0包括进去

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

const int N=2e5+5;
int an,bn,cn,n,a[N],b[N],c[N],mi[N],ans=0x3f3f3f3f;

signed main(){
    read(an);read(bn);read(cn);
    n=an+bn+cn;
    for(int i=1,x;i<=an;i++) read(x),a[x]=1;
    for(int i=1,x;i<=bn;i++) read(x),b[x]=1;
    for(int i=1,x;i<=cn;i++) read(x),c[x]=1;
    for(int i=1;i<=n;i++){
        a[i]+=a[i-1];
        b[i]+=b[i-1];
        c[i]+=c[i-1];
        mi[i]=c[i]-b[i];
    }
    for(int i=n-1;i>=0;i--) mi[i]=min(mi[i+1],mi[i]);
    for(int i=0;i<=n;i++)
        ans=min(ans,(b[i]-a[i])+(an+bn)+mi[i]);
    write(ans);
}
赏

fighter