我的方法时间超限,求更优解法
我的解题思路请见代码注释
题目描述
小明的数学计算能力超强,常常在同学们面前表面得很骄傲。数学科代表实在看不下去了,决定出道很麻烦的题,好好“折磨”他一下。
数学科代表决定给他一些数,让他分组。从第一个数开始分组,且每组必须是连续的一段数,要求每组和相等,问每组和最小可以是多少。(当然这些数一定可以被分组,大不了直接分成一组。)
输入
第一行为一个数N
第二行为N个整数(每个数均小于等于1000),两个数间用空格隔开。
输出
一行,最小的和
样例输入
6
2 5 1 3 3 7
#include<iostream>
using namespace std;
long long n,a[1000002];
int main()
{
cin>>n;
for(long long i=1;i<=n;i++) //输入
{
cin>>a[i];
}
for(long long sum=0;;sum++) //分组的和,从小到大
{
long long s=0,check=0; //一个记录每一个分组的和,一个判断
for(long long i=1;i<=n;i++)
{
s+=a[i]; //进入分组
if(s==sum) //如果分其中一个组的和s相等sum,找下一个分组,和重新变为0
{
s=0;
continue;
}
if(s>sum||(i==n&&s<sum)) //如果其中一个分组的和s超过sum 或者
{ //到了最后一个数时 s不满sum,说明条件不成立
check=1;
break;
}
}
if(check==0) //直接输出,每组和一定最小,见第11行
{
cout<<sum;
return 0;
}
}
return 0;
}