题解：P11886 「Stoi2025」爱你没差

· · 题解

直入主题，注意条件 m \times x \geq y 和 m \times y \geq x （以下简称条件一和条件二），不妨设 x \leq y 。条件二是必定满足的，考虑条件一。

如果 x 不能满足条件一，那么说明 x “小了”，我们希望 x 大“一点点”再来合并，也就是将 x 加上大于等于 x 的最小数。

于是就有了贪心思路。

维护一个小根堆，每次取出顶部的两个数合并，判断能否得分即可。

能否先合并大的数？

不能

如果先合并大的，那么大的数将变得更大，对于其他较小数也就更难得分，因此相较先合并小数更劣。

又有人可能会问：主播主播，如果 x “小了”，能否不增大 x ，而增大一个比 x 更小的数，然后让那个增大的数和 x 合并？

不能

因为我们使用小根堆维护，最先取出的两个数必定是最小的，因此不存在上述问题。

注意事项

由于数据范围过大，直接判断 m \times x \geq y 可能会在 m \times x 处超过 unsigned long long 的范围，因此建议强制转换浮点型并判断等价条件 x \geq \frac{y}{m}

参考代码

#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
inline int read(){
    int s=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*f;
}
int n,m,x,y,s=0;
priority_queue<int,vector<int>,greater<int> >q;
signed main(){
    n=read();
    m=read();
    for(int i=1;i<=n;i++){
        q.push(read());
    }
    while(q.size()>1){
        x=q.top();
        q.pop();
        y=q.top();
        q.pop();
        if(x>=y*1.0/m&&y>=x*1.0/m){
            s++;
        }
        q.push(x+y);
    }
    printf("%llu\n",s);
    return 0;
}