1186: 子序列问题II(前缀和)

本文主要是介绍1186: 子序列问题II(前缀和)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1186: 子序列问题II

菜鸟生成记(77)

水题,不过要加一点点的优化;纯暴力O(n^3)，前缀和预处理一下,O(n*n)

#include<iostream>
#include<cstring>
using namespace std;
int a[11000];
int main()
{int n,s;while(cin>>n>>s){int len1=20000;memset(a,0,sizeof(a));for(int i=1;i<=n;i++){cin>>a[i];a[i]+=a[i-1];//前缀和预处理}//a[x]:a[1]到a[x]的和//a[y]-a[x]:a[x+1]到a[y]的和for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){if(a[j]-a[i]>=s)//区间和大于等于s{//记录区间长度len1=min(len1,j-i);}}}if(len1==20000)cout<<0<<endl;elsecout<<len1<<endl;}return 0;
}

这篇关于1186: 子序列问题II(前缀和)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---