CF1379C Choosing flowers 题解
题意：
有 $m$ 种物品，每种物品有无限个，你可以购买 $n$ 个物品。
对于第 $i$ 种物品：
第一次买时的贡献是 $a_i$ ,接下来每购买一个的贡献都是 $b_i$。即当你买了 $x_i$ 个第 $i$ 种物品时，贡献是 $a_i+b_i \times (x_i-1)$
现在要你求出最大贡献。
输入格式：
第一行一个 $t (1≤t≤10^4)$，表示有 $t$ 组数据。
对于每组数据：
第一行$n$ 和 $m (1≤n≤10^9,1≤m≤10^5)$
接下来 $m$ 行，每行两个整数$a_i$和$b_i(0≤a_i,b_i≤10^9)$
每组数据后有一个空行。
输出格式：
对于每组数据，输出一行一个整数表示最大的贡献。
容易发现，最优解一定只有一种物品被买了多次。
考虑枚举这个物品 $i$ ，如果 $i$ 被买了多次，则其他物品 $k_i$ 一定有 $a_{k_i} > b_i$ ，否则 $i$ 不会被买多次
我们对物品按 $a_i$ 排序并预处理前缀和，然后二分出第一个 $a_k$ 大于 $b_i$ 的 $k$ ，再分类讨论即可。
时间复杂度 $\mathcal{O}(n \log n)$
代码：（别忘了判 $k$ 不存在的情况）
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))
#define Fi first
#define Se second
pii a[N]; int sum[N];
void solve()
{
int n,m; cin >> m >> n;
for(int i = 1; i <= n; i++) { cin >> a[i].Fi >> a[i].Se; }
sort(a + 1, a + 1 + n);
for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i].Fi;
int res = 0;
for(int i = 1; i <= n; i++)
{
int l = 1, r = n;
while(l < r)
{
int mid = (l + r) >> 1;
if(a[mid].Fi > a[i].Se) r = mid; else l = mid + 1;
}
if(a[l].Fi <= a[i].Se) up(res, a[i].Fi + (m - 1) * a[i].Se);
else if(n - l + 1 >= m) up(res, sum[n] - sum[n - m]);
else if(l <= i) up(res, sum[n] - sum[l - 1] + (m - (n - l + 1)) * a[i].Se);
else up(res, sum[n] - sum[l - 1] + a[i].Fi + (m - (n - l + 1) - 1) * a[i].Se);
}
cout << res << '\n';
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int qwq; cin >> qwq; while(qwq--) solve();
return 0;
}参考文献：
