0
已解决
新手守护
问一下，4522，我这条代码怎么简化，如果不对的话，能给点思路吗
#include<iostream>
using namespace std;
int t,n,a[1000005],m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
while(t!=n){
for(int i=1;i<=n-t;i++){
int sum=0;
for(int j=i;j<=i+t;j++){
sum+=a[j];
}
if(sum==m){
cout<<t+1;
return 0;
}
}
t++;
}
}
0
已采纳
中级启示者
n这么大，o(n^3)肯定不行
考虑前缀和优化
先进行前缀和，再暴力枚举区间大小，找出所有可行的区间，如果和>=m，就输出区间大小,return 0;
时间复杂度：o(n^2) ,实际是 o(n*最后答案)
核心
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
if(sum[j]-sum[j-i]>=m){//sum[i]表示前i个金币的和
cout<<i;
return 0;
}
}
}当然还有更优秀的o(nk)的做法（k是常数），这里就不说了
0
修练者
DING。。。
0
修练者
使用暴力枚举，注意时间复杂度和数据范围
