[CF1054C]Candies Distribution

题目：Candies Distribution

传送门：http://codeforces.com/problemset/problem/1054/C

分析：

方法一:

1）类似拓扑排序的做法。

2）当$L_i,R_i$均为$0$时，这个数就是当前最大的数，可以移除并且去掉他带来的影响，即左边的$R_i$减一，右边得$L_i$减一。

3）当$L_i,R_i$均为$0$时，就当这个点入度为$0$，移除影响就相当于去掉与其相邻的边。

#include <bits/stdc++.h>

using namespace std;

const int maxN=;

vector<int> tp;

int n,L[maxN],R[maxN],val[maxN];

int main() {

    scanf("%d",&n);

    for(int i=;i<=n;++i)scanf("%d",L+i);

    for(int i=;i<=n;++i)scanf("%d",R+i);

    int tn=n;

    for(;;){

        tp.clear();

        for(int i=;i<=n;++i)

            if(!L[i] && !R[i]){tp.push_back(i);val[i]=tn;L[i]=R[i]=-;}

        if(tp.size()==)break;

        tn-=tp.size();

        for(auto it:tp){

            for(int i=;i<it;++i)--R[i];

            for(int i=it+;i<=n;++i)--L[i];

        }

    }

    if(tn)puts("NO");

    else{

        puts("YES");

        for (int i=;i<=n;++i)printf("%d ", val[i]);

    }

    return ;

}

方法二：

学到了一种神奇的构造。

4）如果这个序列是存在，第$i$个小朋友分糖数为$ n-(L_i-R_i) $必然是不会冲突的，检查这个序列，判断是否满足题意。

5）这道题事实上在询问有多少小朋友糖比自己多，无论最终分糖方案是什么，得到相同糖的小朋友的分组是一样的。

#include<bits/stdc++.h>

using namespace std;

const int N = ;

int L[N],R[N],res[N];

int main(){

    int n;scanf("%d",&n);

    for(int i=;i<=n;++i)scanf("%d",L+i);

    for(int i=;i<=n;++i)scanf("%d",R+i);

    for(int i=;i<=n;++i)res[i]=n-L[i]-R[i];

    for(int i=;i<=n;++i)

        for(int j=i+;j<=n;++j){

            R[i]-=res[j]>res[i];

            L[j]-=res[j]<res[i];

        }

    for(int i=;i<=n;++i)

        if(L[i]||R[i]){puts("NO");return ;}

    puts("YES");

    for(int i=;i<=n;++i)printf("%d ",res[i]);

    return ;

}

如果保证有合法解，求一种可行解，然后范围又极大，可以用第二种方法直接构造呀

巴特西

[CF1054C]Candies Distribution

最新文章

热门文章