题解：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}

参考代码

CPP

#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;
}

题解：P11886 「Stoi2025」爱你没差

文章操作

注意事项

参考代码

相关推荐

评论

题解：P11886 「Stoi2025」爱你没差