P16239 [蓝桥杯 2026 省 B] 足球训练 题解
Moya_Rao
·
·
题解
真的只有绿吗我感觉评蓝不过分诶。
考虑当前总和为 S 的情况下，对于两个当前实力值分别为 x_1 和 x_2 的人，每次提升实力分别是加 y_1 和 y_2 时，具体让谁加更优。
为了方便，令 S = x_1 \times x_2 \times C，其中 C 是剩下的人的实力值总乘积，在这里可以看做一个大常数。
让 x_1 加，就是 S' = (x_1 + y_1) \times x_2 \times C = \dfrac{x_1 + y_1}{x_1} \times S；让 x_2 加，就是 S'' = x_1 \times (x_2 + y_2) \times C = \dfrac{x_2 + y_2}{x_2} \times S。比较 S' 和 S''，当 S' > S'' 时训练 x_1，否则训练 x_2。
显然我们不需要真的将 S' 和 S'' 两个值都算出来，只需要比较是否 \dfrac{x_1 + y_1}{x_1} > \dfrac{x_2 + y_2}{x_2}，即 \dfrac{y_1}{x_1} > \dfrac{y_2}{x_2}（两边同减去 1）。
此时你就收获了第一步的 60 分做法：由于这些 \dfrac{y}{x} 会随着 x 的增大（y 是不会变的）而减小，我们可以将其逐个扔进优先队列，每次取队头然后放入下一个对应的 \dfrac{y}{x'}，以此类推取前 m 个让其具体 a 值增加，最后把乘积算出来即可。
这样就得到了一个 O(m \log n) 的做法，题目给的 m \le 10^9，满分还是拿不到的，需要优化。
分母变化而分子不变是非常难搞的，而且每次这个分母的变化都是加上分子，倒过来也就是取倒数的话会很好做（每次 +1），而且再考虑倒数的时候还是可以比较大小的，只是原先要较大的现在要较小的。
如何 `check` 呢？很简单，我们只需要对每个 $a_i$ 求出 $\dfrac{a_i}{b_i}$（也就是前面提到的所谓 $\dfrac{x}{y}$），看要多少个这样形式的值才能提升到 $mid$，等价于要算出 $\left \lceil (mid - \dfrac{a_i}{b_i}) \right \rceil$，这也就是个数，算出其总和判断是否 $\le m$ 即可完成 `check`。实现的时候有一个细节就是说可能 $\dfrac{a_i}{b_i} > mid$ 导致求出来的个数为负数，此时要和 $0$ 取 $\max$（不然你真的取负数个嘛）。
由于这里是浮点二分，不能直接用什么 $l < r$、$l \le r$ 作为二分判断，需要一个 $eps = 10^{-7}$ 左右，然后二分终止判断为 $r - l > eps$，即若 $r - l \le eps$ 就当做其相等了（浮点数没有绝对的相等，因为存在精度误差）。
二分后得到了 $res$，就可以知道每个 $a_i$ 具体要加多少了，也就能对应得到最终的 $a'_i$ 了。吗？
并不是这样的！因为可能存在相等情况，所以前面 `check` 函数的判断是 $\le m$，也就是说可能到了最后还剩下一些 $m$ 值没有使用完全。但，有一个非常好的性质，就是说此时一定 $m < n$，否则所有 $a_i$ 都能再拔高一截，求出来的 $res$ 也就不正确了。因此只要你二分写对了，最后的 $m$ 就很小，不会超过 $n$，可以直接套用前面的 $60$ 分做法（优先队列那个）以 $O(n \log n)$ 解决。
最后算答案的时候记得取模哦。
总的时间复杂度是 $O(n K + n \log n)$ 的，$K$ 是浮点二分的次数，大致不超过 $100$ 次。
::::success[code && [submission](https://www.luogu.com.cn/record/280236758)]
```cpp
#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 1e5+5;
const LL MOD = 998244353;
const LD eps = 1e-7;//浮点精度判断参考值
struct node{LL x,y,id;};
bool operator < (const node &A , const node &B){
//自定义比较器，比较 x/y 的大小（优先较小）
return A.x*B.y>B.x*A.y;//十字相乘避免误差
}
LL n,m,a[N],b[N],Ans;
LD l,r,res;
priority_queue<node> q;
//从小到大，用大根堆的话需将比较器反着写
LL read(){
LL su=0,pp=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
return su*pp;
}
bool check(LD p){
LL cnt=0;
for(int i=1;i<=n;i++){
LD t=(LD)(a[i])/(LD)(b[i]);
LL c=ceil(p-t);//个数
cnt+=max(0ll,c);
//个数可能为负，要和 0 取 max
if(cnt>m)return 0;
//不支持这么多次操作，p 值不合法
}return 1;//检测通过，p 值合法
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++)
a[i]=read(),b[i]=read();
l=0,r=2e14,res=0;
int CC=100;
while(r-l>eps){
LD mid=(l+r)/2.0;
if(check(mid))res=mid,l=mid;
else r=mid;
}
//此时二分到了具体值 res
for(int i=1;i<=n;i++){
LD t=(LD)(a[i])/(LD)(b[i]);
LL c=ceil(res-t);//求出个数
c=max(0ll,c);//可能为负
a[i]+=c*b[i];//累加具体个数
m-=c;//总个数减少
q.push({a[i],b[i],i});//等待替补
}
while(m--){//还剩下一些不多的个数
auto [x,y,id]=q.top();q.pop();
a[id]+=b[id];//累加具体值
q.push({a[id],b[id],id});//等待替补
}
Ans=1;
for(int i=1;i<=n;i++)
Ans=Ans*a[i]%MOD;//最后算出乘积
cout<<Ans<<"\n";
return 0;
}
```
::::
如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！