Codeforces 1462D Add to Neighbour and Remove

题意

给一个长度为$n(1\leq n\leq 3000)$的数组$a$，每次操作可以将一个数字加到相邻的数字并在数组中删除这个数字，请问最少的操作，使得数组中各项相等。

分析

首先数组和是一定的，所以最后数组和最后一定可以被数组大小整除。

分析这个操作，发现其本质就是将一段区间的数字加到一个位置上。

$n\leq 3000$，要求的是$n^2$操作，枚举数组大小后保证数组的每一段的和都是数组和除以数组大小，采取前缀和判断即可。

#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define ull unsigned long long
//#define int ll
#define ls st<<1
#define rs st<<1|1
#define pii pair<int,int>
#define rep(z, x, y) for(int z=x;z<=y;++z)
#define repd(z, x, y) for(int z=x;z>=y;--z)
#define com bool operator<(const node &b)const
using namespace std;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int maxn = (ll) 1e6 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
int T = 1;
int a[maxn];
int sum[maxn];

void solve() {
    int n;
    cin >> n;
    int tot = 0;
    rep(i, 1, n)cin >> a[i], sum[i] = sum[i - 1] + a[i], tot += a[i];
    repd(i, n, 1) {
        if (tot % i == 0) {
            int now = tot / i;
            int pre = 0;
            bool flag = true;
            rep(j, 1, n) {
                if (sum[j] - sum[pre] == now) {
                    pre = j;
                } else if (sum[j] - sum[pre] > now) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                cout << n - i << '\n';
                return;
            }
        }
    }
}

signed main() {
    start;
    cin >> T;
    while (T--)
        solve();
    return 0;
}