【问题描述】
宁宁的数学很厉害，每次考试都是满分。数学课代表不满意了，决定出道题考考宁宁，好好“折磨”她一下。
数学课代表决定给她许多数，让她进行分组。从第一个数开始分组，且每组必须是连续的一段数，要求每组和相等，问每组和最小可以是多少。（当然这些数一定可以被分 组，大不了直接分成一组。）
【输入格式】
从文件divide.in中读入数据。第一行为一个整数N
第二行为N个整数（每个数均小于等于1000），两个数间用空格隔开。
【输出格式】
输出到文件divide.out中。一行，最小的和。
【样例输入】
6
2 5 1 3 3 7
【样例输出】
7
【样例说明】
分成三组（2，5） （1，3，3） （7）和为7，不存在比7更小的和。
【子任务】
|
测试点 |
n |
|
测试点 |
n |
|
1 |
n = 10 |
6 |
n = 1000000 |
|
|
2 |
n = 100 |
7 |
n = 1000000 |
|
|
3 |
n = 1000 |
8 |
n = 1000000 |
|
|
4 |
n = 200000 |
9 |
n = 1000000 |
|
|
5 |
n = 200000 |
10 |
n = 1000000 |
分析
暴力枚举每组的分数，然后用二分判断。
代码
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1000001; inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,l,r,ans,maxx; int a[N]; inline bool pd(int lim){ int cur=1; while(cur<=n){ int pos=lower_bound(a+cur,a+n+1,a[cur-1]+lim)-a; if(a[pos]!=a[cur-1]+lim) return false; cur=pos+1; } return true; } int main(){ freopen("divide.in","r",stdin); freopen("divide.out","w",stdout); n=read(); for(int i=1;i<=n;++i){ a[i]=read(); maxx=max(maxx,a[i]); a[i]+=a[i-1]; } for(int i=1;i<=n;++i){ if(a[n]%a[i]!=0||a[i]<maxx) continue; if(pd(a[i])){ans=a[i]; break;} } printf("%d ",ans); return 0; }