D. Add to Neighbour and Remove

D. Add to Neighbour and Remove

传送门

题 意 ： 给 一 个 序 列 ， 你 可 以 将 a i 加 到 a i + 1 或 者 a i − 1 , 操 作 后 a i 消 失 ， 即 题意：给一个序列，你可以将a_i加到a_{i+1}或者a_{i-1},操作后a_i消失，即 题意：给一个序列，你可以将ai​加到ai+1​或者ai−1​,操作后ai​消失，即
序 列 长 度 减 一 ， 问 最 少 操 作 次 数 使 得 每 一 个 元 素 都 相 同 序列长度减一，问最少操作次数使得每一个元素都相同 序列长度减一，问最少操作次数使得每一个元素都相同
分 析 ： 数 据 是 真 的 水 ， 放 心 暴 力 吧 。 对 于 这 个 序 列 ， 我 们 可 以 预 处 理 前 缀 和 ， 然 后 我 们 分析：数据是真的水，放心暴力吧。对于这个序列，我们可以预处理前缀和，然后我们 分析：数据是真的水，放心暴力吧。对于这个序列，我们可以预处理前缀和，然后我们
直 接 枚 举 每 一 部 分 前 缀 和 ， 看 看 结 果 若 干 次 操 作 后 序 列 的 共 同 元 素 是 那 一 部 分 的 前 缀 和 。 直接枚举每一部分前缀和，看看结果若干次操作后序列的共同元素是那一部分的前缀和。 直接枚举每一部分前缀和，看看结果若干次操作后序列的共同元素是那一部分的前缀和。

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <string>
#include <bitset>
#include <vector>
#include<cstring>
#include <stdio.h>
#include <iostream>
#include <algorithm>
/*
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);*/
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
const int maxn = 1e5+5;
ll a[maxn],sum[maxn];
int main()
{int t=read();set<int>st;while (t--){int n=read();int flag=false;ll M=-INF;a[1]=read();sum[1]=a[1];for(int i=2;i<=n;i++){cin>>a[i],sum[i]=sum[i-1]+a[i];if(a[i]!=a[i-1]) flag=true;M=max(M,a[i]);}if(!flag) {puts("0");continue;}for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)st.insert(sum[i]-sum[j-1]);int ans=INF;for(auto i:st){int tmp=i;if(tmp<M) continue;int Sum=0;int cnt=0;bool f=false;for(int j=1;j<=n;j++){if(Sum<tmp) Sum+=a[j];if(Sum==tmp) cnt++,Sum=0;else if(Sum>tmp) {f=true;break;}}if(f||Sum>0&&Sum<tmp) continue;ans=min(ans,n-cnt);}printf("%dn",ans);}return 0;
}