#51833: 經典的滑動視窗!


310002@student.cysh.cy.edu.tw (HO HO HO)

學校 : 國立嘉義高級中學
編號 : 299160
來源 : [114.27.175.124]
最後登入時間 :
2025-07-08 23:12:08

因為都是正整數,所以滑動視窗O(n)即可,令右界和左界一一往後推就好了

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector <int> v(n);
    for (auto &i:v){
        cin >> i;
    }
    //l=左界, r=右界
    int l=0, ans=0, sum=0;
    for (int r=0; r<n; r++){
        sum+=v[r];
        //對於每個右界,若移動後加總大於k則縮減左界
        while(sum>k){
            sum-=v[l];
            l++;
        }

//for+while 看起來O(n^2)但是l, r都只會掃過去一次所以是O(n)
        ans=max(ans, sum);
    }
    cout << ans << '\n';
}