蓝桥杯试题 算法训练 礼物

题目链接
正向思考比较困难，于是想到可以枚举K，寻找最大的满足条件的K，采用二分答案法，时间复杂度O(nlog(n)),不过这个复杂度c++可以过，java过不了呜呜，等再研究一下如何用滑窗解决这个问题

#include 
#include 
using namespace std;
long long sum[1000005]={0};
long long N,S;
bool check(int K){
    for(int i=0;i<=N-2*K;i++){
        if(sum[i+K]-sum[i]<=S && sum[i+2*K]-sum[i+K]<=S){
            return true;
        }
    }
    return false;
}
int main()
{
    cin >> N >> S;
    long long tmp;
    sum[0]=0;
    for(int i=1;i<=N;i++){
        scanf("%lld",&tmp);
        sum[i]=tmp+sum[i-1];
    }
    int left=0,right=N;
    int ans=0;
    while(left<=right){
        int K=left+(right-left)/2;
        if(check(K)){
            ans=2*K;
            left=K+1;
        }else{
            right=K-1;
        }
    }
    cout << ans;
    return 0;
}