问题标题: 酷町堂：4522 吃金币

Question

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++;
    }
}

Answer 1

已采纳

汪恺恒

中级启示者

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是常数），这里就不说了

问题标题: 酷町堂：4522 吃金币

1 个回答: