大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
二分法+前缀和法律
满足子序列长度的条件(0,n)之间,sum[x+i]-sum[i]从i元素开始序列长度x和。前缀和可在O(n)的时间内统计
sum[i]的值。再用二分找出满足条件的最小的子序列长度。
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<queue> #include<set> #include<map> #include<vector> #include<cmath> #define ll __int64 #define INF 0x3fffffff using namespace std; int sum[100005]; int a[100005]; int n,s; bool C(int x) { bool flag=false; for(int i=0;i<n-x;i++) { if(sum[x+i]-sum[i]>=s) { flag=true; break; } } if(flag) return true; else return false; } int solve() { int l=0,r=n+1; while(r-l>1) { int mid=(l+r)/2; if(C(mid)) r=mid; else l=mid; } return r; } int main() { int T; //freopen("d:\\Test.txt","r",stdin); cin>>T; while(T--) { cin>>n>>s; for(int i=0;i<n;i++) { scanf("%d",&a[i]); } sum[0]=a[0]; for(int i=1;i<n;i++) { sum[i]=sum[i-1]+a[i]; } if(solve()==n+1) cout<<"0"<<endl; else cout<<solve()<<endl; } return 0; }
尺取法
(1) 设置两个指针s和t。一開始都指向数列第一个元素。此外sum=0,res=0。
(2) 仅仅要sum<S。就将sum添加一个元素,t加1;
(3) 直到sum>=S,更新res=min(res,t-s);
(4) 将sum减去一个元素。s加1,运行(2)。
上述流程重复地推进区间的开头和末尾,来求取满足条件的最小区间。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m; int a[100005]; void solve() { int res=n+1; int s=0,t=0,sum=0; while(true) { while(t<n&&sum<m) { sum+=a[t++]; } if(sum<m) break; res=min(res,t-s); sum-=a[s++]; } if(res>n) res=0; cout<<res<<endl; } int main() { int T; //freopen("d:\\Test.txt","r",stdin); cin>>T; while(T--) { cin>>n>>m; for(int i=0;i<n;i++) { scanf("%d",&a[i]); } solve(); } return 0; }
版权声明:本文博客原创文章,博客,未经同意,不得转载。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117508.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...