本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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$，则收益为： $$(a_i-b_ix)x$$ $$=a_ix-b_ix^2$$

把第 $i$ 个的票价增加 $1$，就变成了： $$(a_i-b_i(x+1))(x+1)$$ $$=a_i(x+1)-b_i(x+1)^2$$ $$=a_ix+a_i-b_ix^2-2b_ix-b_i$$

发现把第 $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
}