[CF1470A] Strange Birthday Party

[CF1470A] Strange Birthday Party - 带撤销贪心

Description

你有 (n) 个朋友，(m) 种礼物，第 (i) 种礼物的花费为 (c_i)，对于每个人，都要选 ([1,k_i]) 中的一个礼物给他，或者给他 (c_k_i) 的钱，每种礼物只能被送一次，问最小花费。

Solution

一个很费用流的模型，所以应该是带撤销贪心做了

基本贪心：所有 (k_i) 排序，将所有小于当前 (k_i) 的礼物放在一个堆中，如果当前的最小元素比 (c_k_i) 大，就给钱，否则把礼物给他

撤销：假设将 (c_i) 的礼物送给 a，如果送给 b，那么就要给 (c_k_a) 的钱给 a，相当于给 b 送了一个价值为 (c_k_a) 的礼物，因此对每个人 (i)，给他发了礼物后，都在堆中加入一个 (c_k_i) 的元素表示撤销对这个人的操作并且给他钱

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1000005;

struct gift
{
    int id;
    int price;
    bool operator<(const gift &rhs) const
    {
        return price > rhs.price;
    }
    bool operator<=(const gift &rhs) const
    {
        return price >= rhs.price;
    }
};

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<int> k(n + 2), c(m + 2);
    for (int i = 1; i <= n; i++)
        cin >> k[i];
    for (int i = 1; i <= m; i++)
        cin >> c[i];

    priority_queue<gift> heap;
    int pin = 0;
    sort(&k[1], &k[n + 1]);

    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        while (pin < k[i])
            ++pin, heap.push({pin, c[pin]});
        if (heap.top().price <= c[k[i]])
        {
            ans += heap.top().price;
            heap.pop();
            heap.push({0, c[k[i]]});
        }
        else
        {
            ans += c[k[i]];
        }
    }

    cout << ans << endl;
}

signed main()
{
    int t;
    cin >> t;
    while (t--)
        solve();
}