洛谷 P3353 在你窗外闪耀的星星

题意：给定一个宽度w，n个数，每个数有一个权值。窗口可以变换位置，求该窗口能容纳的最大权值。

思路：前缀和+滑动窗口硬算。

总结：一开始感觉是fenwicktree，但是每次查询的区间固定，不需要fenwicktree，不如滑动窗口来的方便。

void solve(){
    int n, w;
    cin >> n >> w;

    vector<int> a(n);
    vector<int> b(n);
    int maxn = 0;
    for (int i = 0; i < n; ++i){
        cin >> a[i] >> b[i];
        maxn = max(maxn, a[i]);
    }

    vector<long long> pref(maxn + 1);
    for (int i = 0; i < n; ++i){
        pref[a[i]] += b[i];
    }
    for (int i = 1; i <= maxn; ++i){
        pref[i] += pref[i - 1];
    }

    long long ans = 0;
    for (int i = w; i <= maxn; ++i){
        ans = max(ans, pref[i] - pref[i - w]);
    }

    cout << ans << endl;
}