CF1462

CF1462

D. Add to Neighbour and Remove - CF1462D

codeforces1462D

题意：

给出一个由n个数组成的数组，现在你可以对这个数组进行如下操作：将数组中的一个元素加到这个元素的两边中的一边，然后将这个元素删掉。若该元素在最左边，那么该元素不能加到左边，因为它的左边已经没有元素了，同理最右边。现在问你最少几次这样的操作可以让整个数组的每个元素都相等。

思路：

由于该题目的数据范围并不是很大，只有 1 e 3 1e3 1e3，所以可以用 n 2 n^2 n2的做法得出结果：求出这个数组的前缀和，我们枚举前 n n n个数作为最终数组每个元素的大小,当找到第一个符合的前缀和,也就是可以通过划分这个数组，让这个数组的每个部分和都是当前枚举的前缀和的时候，可以保证其是最优解，当前的操作数就是答案。由于最差情况也可以通过全部合并得出，所以不存在没有结果的情况。

ac代码：

#include <cstdio>
#include <cstring>const int maxn = 3e3 + 5;int a[maxn], pre[maxn];int main () {int T, n;scanf ("%d", &T);while (T--) {scanf ("%d", &n);for (int i = 0; i < n; ++i) {scanf ("%d", &a[i]);}memset (pre, 0, sizeof pre);pre[0] = a[0];for (int i = 1; i < n; i++) {pre[i] = pre[i - 1] + a[i];}int ans = 0;for (int i = 0; i < n; i++) {int t = 0;bool flag = false;for (int j = 0; j < n; j++) {t = t + a[j];ans++;if (t == pre[i]) {t = 0;ans--;if (j == n - 1) flag = true;} else if (t > pre[i]) break;}if (flag) break;else ans = 0;}printf ("%dn", ans);}return 0;
}