G

周赛0507D题题解

public
Guest May 09, 2025 Never 22
Clone
C++ paste1.cpp 47 lines (46 loc) | 930 Bytes
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