P2707

FiraCode · 2023-06-09 08:42:40 · 题解

题解思路：

因为当钱数是 x 时收益为 \max\{a_i-b_ix, 0\} \times x。

因为这个 \max 不好化简，那么不妨设 a_i - b_i \times x \ge 0。

当第 i 个票价为 x，则收益为：

把第 i 个的票价增加 1，就变成了：

发现把第 i 个票价增加 1，比原来多了 a_i-2b_ix-b_i。

那么就贪心的选多的最多的，即 a_i-2b_ix-b_i 最大的。

扩展完之后再把扩展完的下一个增加的收益放到堆里即可。

CODE:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, k;
int a[100010], b[100010], cnt[100010];
priority_queue<pair<ll, int>> q;
ll ans;//开long long！

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) scanf("%d%d", &a[i], &b[i]);
    for (int i = 1; i <= n; ++i) {
        q.push({a[i] - 2 * b[i] - b[i]});//初始值
    }
    for (int i = 1; q.size() && i <= k; ++i) {
        auto t = q.front();
        q.pop();
        if (t.first < 0) break;
        ans += t.first;//加上这段增加的值
        cnt[t.second]++;//增加了一个
        q.push({a[i] - 2 * (cnt[t.second] + 1) * b[i] - b[i], t.second});//增加完之后放上
    }
    printf("%lld\n", ans);
    return 0;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                ctj
}