原题链接：
/problem/CodeForces-1379C
AC代码：
#include <algorithm>#include <cmath>#include <cstdio>#include <cstring>#include <iostream>#include <map>#include <queue>#include <set>#include <stack>#include <stdio.h>#include <stdlib.h>using namespace std;int INF = 0x3fffffff;typedef long long ll;void __init__(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);}struct Flowers{ll a;ll b;} flo[101010];ll flo_a[101010], sum_a[101010];int main(){__init__();int tt;cin >> tt;while (tt--){ll n, m;cin >> n >> m;for (int i = 0; i < m; i++){cin >> flo[i].a >> flo[i].b;flo_a[i] = flo[i].a;}sort(flo_a, flo_a + m);sum_a[0] = flo_a[0];for (int i = 1; i < m; i++){sum_a[i] = sum_a[i - 1] + flo_a[i];}ll ans = 0;for (int i = 0; i < m; i++){ll rem = n;int pos = upper_bound(flo_a, flo_a + m, flo[i].b) - flo_a;ll nums = min(n, m - pos);ll temp = sum_a[m - 1] - sum_a[m - 1 - nums];rem -= nums;if (rem > 0){if (flo_a[pos] > flo[i].a || pos >= m){temp += flo[i].a;rem--;}temp += flo[i].b * rem;}ans = max(ans, temp);}cout << ans << endl;}return 0;}
贪心算法、因为花的数量的无限的，所以当某类花需要购买多次时，就意味着当前的b是最优的选择，则剩余的都买这类花就行了，也即最多只有一种花会被购买多次。思路大概就是，遍历每种花购买多次的情况，找到大于当前b的所有a购买一次加起来，剩余的花都买成当前b，另须注意如果是最后一种或者当前b的位置小于pos的位置（当前b需要购买第一次）需要再加上当前a的值，最后维护一个ans的最大值就是最终结果。
