题解：AT_abc432_f Candy Redistribution

· · 题解

题意

有 N 个人，第 i 个人有 A_i 颗糖，每次选一个人把他的糖给一些给另外一个人，求最少几次让每个人的糖数相同。

解法

求出每个人的目标糖果数 tgt=\frac{A_1 + \cdots A_N}{N}。如果 tgt 不是整数直接无解。

考虑每个人向所有被他给糖的人连边，边权就是给了多少个。

发现每种操作图都可以转换为一些链，也就是链是最优的，这样就可以方便的 dp：

:::info[方法] 显然有环是不优的，因为可以将环上所有边减去环上边权的最小值，环就断了。所以它变成了一个 DAG。

将每个点的出度改为 0 或 1：

（虽然这会导致其他点的出度增加，但由于是 DAG，只需要按照拓扑序修改即可。）

同理将每个点的入度改为 0 或 1：

于是操作图就变成了一些链。 :::

设 sum_i 表示集合 i 中的人一共有几颗糖。

设 dp_i 表示现在被加入链中的人的集合为 i 的最小操作次数，dpf_i 表示链尾是第几个人。假设集合 i 中，除了 dpf_i 这个人之外，都分配到了 tgt 颗糖。

枚举链尾进行转移，如果 sum_{i-dpf_i}=tgt\times(|i|-1)，也就是前 |i|-1 个人刚好平均分，则 dp_i=dp_{i-dpf_i}，否则 dp_i=dp_{i-dpf_i}+1。

方案就是 dpf_{i-dpf_i} 给 dpf_i 糖。

代码

#include<bits/stdc++.h>
#define ll long long
#define M 998244853
using namespace std;
int dp[1100000],dpf[1100000];
int sum[1100000];
vector<tuple<int,int,int> > vo;
int a[30];
int tgt;
int n;
int lb(int x){
    return x&-x;
}
void sol(int x){
    int prv=x-(1<<dpf[x]-1);
    if(prv==0) return ;
    sol(prv);
    int popc=__builtin_popcount(prv);
    if(sum[prv]!=tgt*popc) vo.push_back(make_tuple(dpf[prv],dpf[x],sum[prv]-tgt*popc));
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) tgt+=a[i];
    if(tgt%n!=0){
        printf("-1\n");
        return 0;
    }
    tgt/=n;
    for(int i=1;i<=n;i++) sum[1<<i-1]=a[i];
    for(int i=1;i<(1<<n);i++) sum[i]=sum[lb(i)]+sum[i-lb(i)];
    for(int i=1;i<(1<<n);i++){
        dp[i]=1e9;
        int popc=__builtin_popcount(i);
        if(sum[i]<tgt*popc) continue;
        for(int j=1;j<=n;j++){
            if((i>>j-1)&1){
                int tdp=dp[i-(1<<j-1)];
                if(sum[i-(1<<j-1)]!=tgt*(popc-1)) tdp++;
                if(dp[i]>tdp){
                    dp[i]=tdp;
                    dpf[i]=j;
                }
            }
        }
    }
    sol((1<<n)-1);
    printf("%d\n",vo.size());
    for(auto i:vo){
        printf("%d %d %d\n",get<0>(i),get<1>(i),get<2>(i));
    }
    return 0;
}