题解：AT_abc432_f [ABC432F] Candy Redistribution
__czy
·
·
题解
这是一道 DP 题，让我这个蒟蒻来练习一下 DP
题意： 有 N 个小朋友，编号从 1 到 N。
第 i 个小朋友手里有 A_{i} 颗糖果。
你的任务是通过尽可能少的操作，让最终 N 个小朋友手里的糖果数都一样。
- 每次操作，选出两个不同的小朋友 x,y，再选一个正整数 z(不超过第 x 个小朋友手里的糖果数)。从第 x 个小朋友那里拿走 z 颗糖果，给到第 y 个小朋友手里。
请判断是否存在一系列操作，使得最终所有 N 个小朋友的糖果数相同。如果存在，请找出操作次数最少的一组方案。
思路：
首先判断无解的情况：如果糖果的总数不是 n 的正整数倍，那么一定没法让没过小朋友的糖果数相同，输出 -1。
那么有解的情况怎么办呢，首先一种常见的处理方法就是，先把原来的值减去平均值，然后看一下怎么能把每个数都变成 0。
然后好像又没啥思路了……
但是有一个非常显然的贪心是，每一个总和（减去平均值后）为 0 的一段，最优情况下最多的操作次数就是这个段的长度减一。为什么呢，我们考虑把这一段的全部正数都加到一个负数上，然后在把这个数多出来的分给其他负数，那么这样就都是 0 了，这样就只有段的长度减一次操作了。
知道这个贪心后，一个暴力就出来了，我全排列一下，看一看每种排列的最小操作次数是多少，就解决问题了。
但是这样的复杂度显然是不正确的，发现瓶颈就是枚举全排列的这一过程。
考虑优化
我们可以用 DP 来实现这个过程。
我们考虑状态压缩。
那么转移就很好想了，但是有点难描述，不明白的可以看看代码的实现。
## 代码
```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;
}
```
~~大部分代码没啥用处~~
## 温馨提示
这里状态压缩的时候，$i$ 的循环最好从 $0$ 开始，但是输入的时候下标要从 $0$ 并且输出的时候要加上一。（算是警示后人了，自己调了好久）。