题解：AT_abc432_f Candy Redistribution

题意

有

N

个人，第

i

个人有

A_i

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

解法

求出每个人的目标糖果数

tgt=\frac{A_1 + \cdots A_N}{N}

。如果

tgt

不是整数直接无解。

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

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

方法

显然有环是不优的，因为可以将环上所有边减去环上边权的最小值，环就断了。所以它变成了一个 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

糖。

代码

CPP

#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;
}

题解：AT_abc432_f Candy Redistribution

文章操作

题意

解法

代码

相关推荐

评论

题解：AT_abc432_f Candy Redistribution