题目链接：https://www.lanqiao.cn/problems/3541/learning/

个人评价：难度 3 星（满星：5）
前置知识：贪心，结构体

---

整体思路

• 根据题目名可知，虽然题目问的是“至少需要准备多少钱”，但实际要求的是“最大开支”，即所有人都按最贵的方式选择项目；
• 由于参与项目的人数不同将决定项目的单价，不能直接按单价贪，考虑按增量贪心，即：如果第 $i$ 个项目新加入一个成员，需要选择对答案增量最大的项目，这样才能使最终开支最大；
• 首先计算在第 $x$ 名成员加入第 $i$ 个项目之前需要的开支 $before$，即：

$$before=\{\begin{array}{ll}0& x=1\\ \max (K_i(x-1)+B_i,0)\times (x-1)& x\ne 1\end{array}$$

• 其次计算第 $x$ 名成员加入第 $i$ 个项目之后需要的开支 $after$：

$$after=\max (K_i\times x+B_i,0)\times x$$

• $after-before$ 就是第 $x$ 个成员加入后的增量，每个成员贪心取最大的增量，使用优先队列维护即可。

过题代码

#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int maxn = 100000 + 100;
struct Node {LL k, b, x, d;Node() {}// 计算增量 dNode(LL k, LL b, LL x) : k(k), b(b), x(x) {LL before = 0;if (x != 1) {before = max(k * (x - 1) + b, 0LL) * (x - 1);}d = max(k * x + b, 0LL) * x - before;}
};bool operator<(const Node &a, const Node &b) {return a.d < b.d;
}int n, m, k, b;
LL ans;
priority_queue<Node> que;int main() {
#ifdef ExRocfreopen("test.txt", "r", stdin);
#endif // ExRocios::sync_with_stdio(false);cin >> n >> m;for (int i = 1; i <= m; ++i) {cin >> k >> b;que.push(Node(k, b, 1));}for (int i = 1; i <= n; ++i) {Node tmp = que.top();que.pop();// 如果增量 <= 0，说明再取将会减少答案，此时让后面的人不再参与项目才能得到最大开支if (tmp.d <= 0) {break;}ans += tmp.d;tmp = Node(tmp.k, tmp.b, tmp.x + 1);que.push(tmp);}cout << ans << endl;return 0;
}