题解：P16239 [蓝桥杯 2026 省 B] 足球训练
vegetableYe
·
·
题解
题意：
给定 n 对 pair<x,y>，限定你可以恰好做 m 次操作，每次是选一个 pair 执行 x+=y。
最大化操作结束后的，这些 pair 的 x 的乘积（\bmod 998,244,353）。
### 题解：
首先我们要先确定出给谁操作才是最优的，直接手玩样例是不简单的，其实我们可以用 $n=2$ 的小数据手玩。
我们可以先令 $m=1$，看能不能发现什么规律。
例如 $\{x=1,y=3\},\{x=1,y=100\}$，那我们肯定是操作后者，把第二个 `pair` 变成 $\{x=101,y=100\}$。
这样看上去似乎是操作 $x$ 比较大的。但当第二个 `pair` 换成 $\{x=100,y=100\}$ 的时候，此时我们发现操作第一个反倒更好。
如果你看懂了这个简单的例子，你就会发现我们每次操作的那个 `pair`，不一定非得要增量 $y$ 是最大的，而应该让**增幅**最大。
让我们用下面这个更一般化的例子看一看：
现在有 $n$ 个 `pair`，现在我们要决策当前这次操作给 $i=1$ 还是 $i=2$。也就是说，原本的乘积是：某定值 $S \times x_1\times x_2$（其中 $S$ 表示其余 $n-2$ 个 $x$ 的乘积），现在我们让 $x_1$ 变成 $x_1+y_1$，贡献变成了：
$$
(x_1+y_1)\times x_2\times S
$$
如果我们给 $x_2$ 操作，那么贡献会反过来变成：
$$
(x_2+y_2)\times x_1\times S
$$
假设最终给 $x_1$ 操作更好，也就是说：$(x_1+y_1)\times x_2\times S > (x_2+y_2)\times x_1\times S$ 的话，我们推导一下。
两边的 $S$ 显然可以直接约掉，然后把左边的 $x_2$ 除到右边，右边的 $x_1$ 除到左边，式子变成了：
$$
\frac{x_1+y_1}{x_1} > \frac{x_2+y_2}{x_2}
$$
显然，化简后变成了：
$$
\frac{y_1}{x_1} > \frac{y_2}{x_2}
$$
也就是说：**我们一定是把操作给到 $\frac{y}{x}$ 最大的那个 `pair` 上**。
于是我们简单得到了 $60$ 分做法，我们用优先队列存储所有的 `pair`，每次操作最优的进行贪心，维护时按照 $\frac{y}{x}$ 从大到小，因此用大根堆。（当然，这里为了避免精度问题，最好是把除法变成乘法）
但 $100$ 分怎么拿呢？这其实是非常经典的 trick，我们来介绍一下。
首先为了后面好处理，我们先把排序的规则改成按照 $\frac{x}{y}$ 从小到大（这和按 $\frac{y}{x}$ 从大到小本质一样）。
此时我们会发现，操作一定会选择 $\frac{x}{y}$ 最小的那个进行，于是：**在最优的 $m$ 次操作过程中，整个序列中 $n$ 个 `pair` 里的 $\frac{x}{y}$ 的最小值一定是单调不降的。因为我们每次选的是最小的那个操作，然后操作它之后，他的 $\frac{x}{y}$ 就会增大。**
于是，我们就可以考虑直接二分所有操作结束后的：$\min(\frac{x}{y})$ 的最大值。（二分最小值的最大值）
这样一来，对于某个 `pair`，如果其 $\frac{x}{y}$ 值小于我们二分出来的 $mid$，则我们就要不停操作这个 `pair`，直到它的值 $\geq mid$，这样一来，对于每个 `pair`，我们就可以在 $O(1)$ 的时间内把它应做的所有操作都做完。（简单推个式子即可）
于是我们以任意顺序处理完所有 $n$ 个 `pair` 即可，但这里又出现了新的问题，实际上有可能在所有 `pair` 都操作到不小于 $mid$ 后，$m$ 还可能有剩下的，这个问题出现的原因就好比：$\{2,2,2\}$ 和 $\{2,3,3\}$ 这两个数组的最小值都是 $2$ 一样。
但这时，我们一定可以证明的是，此时的 $m$ 在给所有 `pair` 都操作到其 $\frac{x}{y}\geq m$ 后，$m$ 一定严格小于 $n$。
这是因为，如果 $m\geq n$，那就意味着：我们至少可以把 $n$ 个 `pair` 每人都再操作一次，于是当前二分出来的 $mid$ 一定不是最优解对应的 $mid$。（最优解的 $mid$ 肯定能更大）
**因此只要我们二分出来的 $mid$ 就是最优解对应的 $mid$，则 $m<n$ 一定成立。**
而我们发现此时 $m$ 其实已经非常小了，我们直接无脑套用 $60$ 分做法即可。（即优先队列 $O(m\times \log m)$ 模拟）
详见代码：（实现上有些细节，例如我们二分的本质上是浮点数，于是可以直接暴力二分 $100$ 次，这样能避免精度问题可能产生的死循环问题。）
```cpp
struct Node {
int x, y, id;
bool operator<(const Node & n) const {
int nx = n.x, ny = n.y;
// nx / ny < x / y;
return nx * y < x * ny;
}
};
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n + 1), b(n + 1);
for(int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
}
auto check = [&](double mid) {
int C = 0; // 要使得所有 pair 的 x/y 不小于 mid，总共需要至少做 C 次操作
for(int i = 1; i <= n; i++) {
double v = (double)a[i] / (double)b[i];
int cur = (int)ceil(mid - v);
cur = max(0LL, cur);
C += cur;
if(C > m) return 0;
}
return 1;
};
int cnt = 100;
double l = 0, r = 2e14;
while(cnt--) {
double mid = (l + r) / 2;
if(check(mid)) l = mid;
else r = mid;
}
priority_queue<Node> q;
for(int i = 1; i <= n; i++) {
double v = (double)a[i] / (double)b[i];
int cur = (int)ceil(l - v);
cur = max(0LL, cur);
a[i] += cur * b[i];
m -= cur;
q.push({a[i], b[i], i});
}
while(m--) {
auto [x, y, id] = q.top();
q.pop();
a[id] += y;
q.push({a[id], y, id});
}
int ans = 1;
for(int i = 1; i <= n; i++) {
assert(a[i] <= 1e18);
a[i] %= MOD;
ans = (ans * a[i]) % MOD;
}
cout << ans << endl;
}
```
时间复杂度：$O(n\times K)$。（其中 $K=100$ 为固定的二分次数）