2023年3月10日 https://codeforces.com/problemset/problem/1379/C

输入 t(≤1e4) 表示 t 组数据。所有数据的 m 之和 ≤1e5。

每组数据输入 n(≤1e9) m(≤1e5) 表示有 m 种物品，每种物品有无限个，
你需要选择 n 个。
然后输入 m 行，每行两个数字 a[i] 和 b[i]，范围在 [0,1e9]。

如果第 i 种物品选 x 个（x>0），收益为 a[i]+(x-1)*b[i]。
输出最大收益。

输入
2
4 3
5 0
1 4
2 2

5 3
5 2
4 2
3 1
输出
14
16

如果选择的物品足够多 那么我后面一定只会盯着 b[i]最大的那个拿 （贪心） 题目隐藏的关键点

那么如果盯着b[i]走 a 中 比b[i]大的可以提前先拿 怎么判断呢？ -> 可以排序加二分

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 100010;
int n, m;
PII a[N];

int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        cin >> n >> m;
        vector<int> v;
        v.push_back(0);
        for(int i = 1; i <= m; i ++){
            cin >> a[i].first >> a[i].second;
            v.push_back(a[i].first);
        }
        sort(v.begin(), v.end());
        vector<LL> s(m + 1, 0);
        for(int i = 1; i <= m; i ++) s[i] = s[i - 1] + v[i];

        LL res = 0;
        for(int i = 1; i <= m; i ++)
        {
            int cnt = n;
            int l = 1, r = m;
            while(l < r){
                int mid = (l + r) / 2;
                if(v[mid] >= a[i].second) r = mid;
                else l = mid + 1;
            }
            LL sum = 0;
            if(v[r] < a[i].second){ //手写二分要注意边界问题
                if(cnt > 0)
                {
                    sum = (sum + a[i].first + (LL)(cnt - 1) * a[i].second);
                    res = max(res, sum);
                }
                continue;
            }
            int len = min(cnt, m - r + 1);
            sum += s[m] - s[m - len];
            cnt -= len;
            if(cnt == 0){
                res = max(res, sum);
            }
            else{
                if(v[r] > a[i].first){
                    cnt --;
                    sum += a[i].first;
                }
                sum += (LL)cnt * a[i].second;
                res = max(res, sum);
            }
        }
        printf("%lld\n", res);
    }
    return 0;
}