题目链接：https://codeforces.com/contest/1379/problem/C
题意
有 $m$ 种花，每种花数量无限，第一次购买一种花收益为 $a_i$，之后每一次购买收益为 $b_i$，问买 $n$ 朵花的最大收益为多少。
题解
感觉是个 $dp$，实际上是个贪心。
一定是一种花买了很多，其他花不买或只买一次，当其他花第一次购买的收益 $a_j$ 大于要买较多花的 $b_i$ 时，可以将一个 $b_i$ 换为其他花的 $a_j$ 。
枚举哪种花买的较多，然后在 $a$ 中二分该花的 $b_i$，并用前缀和计算可以增加的收益即可。
代码
#include <bits/stdc++.h> using ll = long long; using namespace std; constexpr int N = 1e5 + 100; int n, m; ll sum[N]; pair<int, int> a[N]; ll getans(int i) { //第一个大于 b[i] 的 a[j] 的位置 int j = upper_bound(a + 1, a + 1 + m, make_pair(a[i].second, 0)) - a; //如果可以替换所有当前花的所有 b[i]，那么返回最大的 n 个 a[j] 的和即可 if (m - j + 1 >= n) { return sum[m - n + 1]; } //剩余的 b[i] 个数，-1 是减去第一次购买的 a[i] int rest = n - (m - j + 1) - 1; //如果 j <= i，此时 a[i] 已经在 sum[j] 里计入过一次了，多出来的买为 b[i] 即可 if (j <= i) { ++rest; return 1LL * rest * a[i].second + sum[j]; } return 1LL * rest * a[i].second + sum[j] + a[i].first; } void solve() { cin >> n >> m; for (int i = 1; i <= m; ++i) { cin >> a[i].first >> a[i].second; } sort(a + 1, a + 1 + m); sum[m + 1] = 0; for (int i = m; i >= 1; --i) { sum[i] = sum[i + 1] + a[i].first; } ll ans = 0; for (int i = 1; i <= m; ++i) { ans = max(ans, getans(i)); } cout << ans << " "; } int main() { int t; cin >> t; while (t--) solve(); }