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;
}参考文献：
