AtCoder Beginner Contest 249 F - Ignore Operations // 贪心 + 大根堆

传送门：F - Keep Connect (atcoder.jp)

题意：

给定长度为N的操作（ti，yi）。

给定初值为0的x，对其进行操作：当t为1时，将x替换为y；当t为2时，将x加上y。

最多可以跳过k步，求最终x的最大值。

思路：

注意到，当t为1时，进行替换操作，那么该位置前面的操作是不会对后面产生任何影响的，也就不会消耗k。

那么我们可以枚举最后一次不跳过的1操作，对于该位置的前面无需考虑，对于该位置的后面：所有的1操作都应跳过（记数量为cnt），且对于2操作选择数值前k - cnt小的跳过。

于是可以从后往前推，同时维护一个大小为k - cnt的大根堆（存跳过的2操作的数值），和一个增加值add（存不跳过的2操作的数值之和），则当每次遇到1操作时，此时的x值为（y + add），动态更新求最大值即可。

代码参考：

#include <bits/stdc++.h>

#define LL long long

#define PII pair<int,int>

#define fi first

#define se second

using namespace std;

const int N = 200010;

int n, k;

PII a[N];

priority_queue<int> heap;

// 维护大根堆

void func(LL& add)

{

    while(heap.size() > k) {

        add += heap.top();

        heap.pop();

    }

}

int main()

{

    cin >> n >> k;

    for(int i = n; i; i--) cin >> a[i].fi >> a[i].se;

    LL ans = -1LL << 60, add = 0;

    for(int i = 1; i <= n; i++) {

        int t = a[i].fi, y = a[i].se;

        if(t == 1) {

            ans = max(ans, y + add);

            -- k;

            func(add);

        }

        if(t == 2) {

            if(y >= 0) add += y;

            else heap.push(y);

            func(add);

        }

        if(k < 0) break;

    }

    if(k >= 0) ans = max(ans, add);

    cout << ans << endl;

    return 0;

}

巴特西

AtCoder Beginner Contest 249 F - Ignore Operations // 贪心 + 大根堆

最新文章

热门文章