题解 CF297C Splitting the Uniqueness

Aiopr_2378 · 2022-07-27 19:43:50 · 题解

题目大意：

给定 n 个互不相同的非负整数数列 s 。构造两个非负整数数列 a 与 b。使得 a_i+b_i=s_i。使得每个数列最多有 \left\lfloor\dfrac{S}{3}\right\rfloor 个数重复。

其中，n\leq10^5\;,\;0\leq s_i\leq10^9。

构造方法：

我们分成三段考虑问题。我们的目标是至多让 \left\lfloor\dfrac{S}{3}\right\rfloor 个数重复。我们可以按照如下方法构造：

将 s[i] 按照数值大小排序后，设 k=\left\lceil\dfrac{S}{3}\right\rceil，

• 对于第一段，即 1\leq i\leq k时，我们构造

• 对于第二段，即 k+1\leq i\leq n-k 时，我们构造

• 对于第三段，即 n-k+1\leq i\leq n 时，我们构造

如果上面的形式不直观，可以看下面的图片辅助理解。

红色表示 a_i，蓝色表示 b_i，可以看到，最多有 \left\lfloor\dfrac{S}{3}\right\rfloor 个重复。

参考代码：

#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 100005
struct node{
    int a,b,c,id;
}s[MAXN];
int n;
bool cmp(node x,node y){
    return x.a<y.a;
}
bool cmp2(node x,node y){
    return x.id<y.id;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i].a;
        s[i].id=i;
    }
    sort(s+1,s+1+n,cmp);
    int t=n/3+(n%3!=0);
    for(int i=1;i<=t;i++){
        s[i].b=i-1;
        s[i].c=s[i].a-s[i].b;
    }
    for(int i=t+1;i<=n-t;i++){
        s[i].c=i-1;
        s[i].b=s[i].a-s[i].c;
    }
    for(int i=n-t+1;i<=n;i++){
        s[i].c=n-i;
        s[i].b=s[i].a-s[i].c;
    }
    sort(s+1,s+1+n,cmp2);
    puts("YES");
    for(int i=1;i<=n;i++) cout<<s[i].b<<" ";
    puts("");
    for(int i=1;i<=n;i++) cout<<s[i].c<<" ";
    return 0;
}