CF1774D 题解

· · 题解

题意

给出 m 个长度为 n 的数组，数组中每个数不是 0 就是 1。你可以选择任意两个数组交换 pos 位置上的数。请构造一种交换方案，使得操作数最少，并且操作完成后每个数组中 1 的个数相等。

思路

贪心思路其实挺好想的。

要让每个数组 1 的个数相等，我们需要算出所有 1 的和 sum，每个数组要有 \frac{sum}{n} 个 1。如果 \frac{sum}{n} 不是整数，也就是不能被整除，那么直接输出 -1。

每次交换只能选择两个数组。先统计出一个数组中 1 的个数 cnt。对于位置 pos，每次都要遍历每个数组。对于以下两种情况：

注意在位置 pos 上要有两个数组分别满足这两个情况的其中一个，才可以交换。容易证明，只要 sum 是 n 的倍数，就可以通过交换使得每个数组中 1 的个数相等。

代码

void solve(){
    scanf("%d%d",&n,&m);
    init();
    for(int i=0;i<n;i++){
        int tmp=0;
        for(int j=0;j<m;j++){
            int x;scanf("%d",&x);
            a[i].push_back(x);
            sum+=x,tmp+=x;
        }
        cnt.push_back(tmp);
    }
    if(sum%n!=0){
        puts("-1");
        return;
    }
    sum/=n;
    for(int i=0;i<m;i++){
        locmore.clear(),locless.clear();
        for(int j=0;j<n;j++){
            if(cnt[j]>sum&&a[j][i])locmore.push_back(j);
            if(cnt[j]<sum&&!a[j][i])locless.push_back(j);
        }
        int len=min(locmore.size(),locless.size());
        for(int j=0;j<len;j++){
            ans[++tot]=(node){locless[j],locmore[j],i};
            cnt[locmore[j]]--,cnt[locless[j]]++;
        }
    }
    printf("%d\n",tot);
    for(int i=1;i<=tot;i++)printf("%d %d %d\n",ans[i].x+1,ans[i].y+1,ans[i].z+1);
}