专栏文章

题解：AT_abc432_f [ABC432F] Candy Redistribution

___czy
AT_abc432_f题解参与者 5已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@min2mw9v
此快照首次捕获于
2025/12/01 19:34
3 个月前
此快照最后确认于
2025/12/01 19:34
3 个月前
查看原文

这是一道 DP 题，让我这个蒟蒻来练习一下 DP

题意： 有 NN 个小朋友，编号从 11 到 NN。
第 ii 个小朋友手里有 AiA_{i} 颗糖果。
你的任务是通过尽可能少的操作，让最终 NN 个小朋友手里的糖果数都一样。
  • 每次操作，选出两个不同的小朋友 x,yx,y，再选一个正整数 zz(不超过第 xx 个小朋友手里的糖果数)。从第 xx 个小朋友那里拿走 zz 颗糖果，给到第 yy 个小朋友手里。
请判断是否存在一系列操作，使得最终所有 NN 个小朋友的糖果数相同。如果存在，请找出操作次数最少的一组方案。
思路：
首先判断无解的情况：如果糖果的总数不是 nn 的正整数倍，那么一定没法让没过小朋友的糖果数相同，输出 −1-1。
那么有解的情况怎么办呢，首先一种常见的处理方法就是，先把原来的值减去平均值，然后看一下怎么能把每个数都变成 00。
然后好像又没啥思路了……
但是有一个非常显然的贪心是，每一个总和（减去平均值后）为 00 的一段，最优情况下最多的操作次数就是这个段的长度减一。为什么呢，我们考虑把这一段的全部正数都加到一个负数上，然后在把这个数多出来的分给其他负数，那么这样就都是 00 了，这样就只有段的长度减一次操作了。
知道这个贪心后，一个暴力就出来了，我全排列一下，看一看每种排列的最小操作次数是多少，就解决问题了。
但是这样的复杂度显然是不正确的，发现瓶颈就是枚举全排列的这一过程。

考虑优化

我们可以用 DP 来实现这个过程。
我们考虑状态压缩。
fSf_{S} 表示已经确定集合 SS 的排列后最多能把原数列分成几个总和是 00 的段。
那么转移就很好想了，但是有点难描述，不明白的可以看看代码的实现。

代码

CPP
#include <bits/stdc++.h>
#define fi first
#define se second
#define mkp make_pair
#define pii pair<int, int>
#define ls(k) z[k].son[L]
#define rs(k) z[k].son[R]
#define lson ls(k), l, mid
#define rson rs(k), mid + 1, r
#define ui unsigned int
#define ull unsigned long long
#define lb lower_bound
#define ub upper_bound
#define mii map<int, int>
#define mll map<ll, ll>
#define mset multiset
#define low(k) (k) & (-(k))
using namespace std;
typedef long long ll;
const int L = 0, R = 1;
const int N = 21;
int f[1 << N], sum[1 << N], pos[1 << N];
int n, avg;
int a[N];
vector<int> p;
inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch <= '9' && ch >= '0'){
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}
inline void write(int x)
{
  if(x < 0)
    putchar('-'),x = -x;
  if(x > 9)
    write(x / 10);
  putchar(x % 10 + '0');
  return;
}
int main(){
	n = read();
	for(int i = 0; i < n; ++i){
		a[i] = read();
		avg += a[i];
	} 
	if(avg % n != 0){
		puts("-1");
		return 0;
	}
	avg /= n;
	for(int i = 0; i < n; ++i)
		a[i] -= avg;
	for(int S = 1; S < (1 << n); ++S){
		for(int i = 0; i < n; ++i){
			if((S >> i) & 1){
				sum[S] = sum[S ^ (1 << i)] + a[i];
				int c = (sum[S] == 0);
				if(f[S ^ (1 << i)] + c >= f[S]){
					f[S] = f[S ^ (1 << i)] + c;
					pos[S] = i;
				}
			}
		}
	}
	int now = (1 << n) - 1;
	cout << n - f[now] << '\n';
	while(now){
		p.push_back(pos[now]);
		now ^= (1 << pos[now]);
	}
	reverse(p.begin(), p.end());
	for(int l = 0, r; l < p.size(); l = r + 1){
		r = l;
		int tmp = a[p[l]];
		while(tmp != 0){
			r++;
			tmp += a[p[r]];
		}
		int neg = -1;
		for(int i = l; i <= r; ++i)
			if(a[p[i]] < 0){
				neg = i;
				break;
			}
		for(int i = l; i <= r; ++i){
			if(a[p[i]] > 0 && i != neg){
				cout << p[i] + 1 << ' ' << p[neg] + 1 << ' ' << a[p[i]] << '\n';
				a[p[neg]] += a[p[i]];
				a[p[i]] = 0;
			}
				
		}
		for(int i = l; i <= r; ++i){
			if(a[p[i]] < 0 && i != neg){
				cout << p[neg] + 1 << ' ' << p[i] + 1 << ' ' << -a[p[i]] << '\n';
				a[p[neg]] -= a[p[i]];
				a[p[i]] = 0;
			}
		}
	}
	return 0;
}
大部分代码没啥用处

温馨提示

这里状态压缩的时候，ii 的循环最好从 00 开始，但是输入的时候下标要从 00 并且输出的时候要加上一。（算是警示后人了，自己调了好久）。

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...