周赛0507D题题解
public
May 09, 2025
Never
22
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=3e5+1; 4 int n; 5 long long a[maxn];//输入 6 long long s; 7 long long sum[maxn];//前缀和 8 9 int main(){ 10 ios::sync_with_stdio(NULL); 11 cin.tie(nullptr);cout.tie(nullptr); 12 int t;cin>>t; 13 while(t--){ 14 cin>>n>>s; 15 for(int i=1;i<=n;++i){ 16 cin>>a[i]; 17 sum[i]=sum[i-1]+a[i]; 18 } 19 if(sum[n]<s){ 20 cout<<0<<endl;//提前判断不可能 21 }else{ 22 int l=1,r=n,mid=(1+n)/2; 23 int lastl=l,lastr=r;//此处用来判断是否死循环 24 while(!(l>=r-1&&l!=1)){//冗余环节,懒得删 25 bool b=false; 26 mid=(l+r)/2; 27 for(int i=1;i+mid-1<=n;++i){ 28 if(b)break; 29 long long e=sum[i+mid-1]-sum[i-1]; 30 if(e>=s){ 31 b=true; 32 } 33 } 34 if(b){ 35 r=mid; 36 }else{ 37 l=mid; 38 } 39 if(l==lastl&&r==lastr)break; 40 lastl=l,lastr=r; 41 } 42 cout<<r<<endl; 43 } 44 } 45 return 0; 46 } 47 //l=1,r=5,mid=3,n=5