题目描述

小明的数学计算能力超强，常常在同学们面前表面得很骄傲。数学科代表实在看不下去了，决定出道很麻烦的题，好好“折磨”他一下。

数学科代表决定给他一些数，让他分组。从第一个数开始分组，且每组必须是连续的一段数，要求每组和相等，问每组和最小可以是多少。（当然这些数一定可以被分组，大不了直接分成一组。）

输入

第一行为一个数$N$

第二行为$N$个整数（每个数均小于等于1000），两个数间用空格隔开。

输出

一行，最小的和

样例输入输出

输入#1

6

2 5 1 3 3 7

输出#1

7

输入#2

6

1 1 2 3 2 3

输出#2

12

提示

【样例1说明】

分成三组（2，5） （1，3，3） （7） 和为7，不存在比7更小的和。

【数据规模】

测试点 $n$

1	n=10
2	n=100
3	n=1000
4	n=200000
5	n=200000
6	n=1000000
7	n=1000000
8	n=1000000
9	n=1000000
10	n=1000000

这道题正解是什么？

#include<bits/stdc++.h>
using namespace std;
long long s,minsum=1e+15;
int a[1000001],n,i;
bool find(long long I){
    long long cnt=0;
    for(i=1;i<=n;i++){
        cnt+=a[i];
        if(cnt>I)return 0;
        if(cnt==I)cnt=0;
    }
    return 1;
}
int main()
{
    scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&a[i]);s+=a[i];}
    for(long long i=1;i*i<=s;i++){
        if(find(i))minsum=min(minsum,i);
        if(find(s/i))minsum=min(minsum,s/i);
    }
    cout<<minsum;
}

数据有点水，这个暴力枚举每种可能的答案的代码都能过（还是本来就能过？）

如果本来就能过，能不能说明一下最劣的情况，以及时间复杂度

如果不行，各位大佬能不能提供一下正解的思路

谢谢！