[NOIP2025] 糖果店 题解

感觉我永远出不来这种题。

怎么现在还没有题解，让我复活一下写一下这个祝我破顶的题吧！

我尽量讲清楚一点。

贪心。

怎么看出来的？观察数据范围，这玩意是非常非常大的，排除dp，而这种“最大值”的做法（准确来说是策略性）无非就几种：二分，dp，贪心。二分显然不对（你想，这个怎么 check？还是绕了个圈圈！），所以我们想到贪心。

观察每种糖果取多次的结果，发现总是（奇数+偶数）*若干次+奇数。形式化地，假设买 $a$ 轮（一轮两个），那么他的答案只会是 $(x_i+y_i)\times a$ 或者 $(x_i+y_i)\times a+x_i$。

是不是正解要出来了？去花钱买大的 $(x_i+y_i)$，还不如去买最小的 $(x_j+y_j)$！这就是特殊性质 A 的做法！

于是我们得到下面策略（记 $x+y$ 最小的那个地方是 $k$）：

如果要买“2”，直接去 $k$ 去买。买“1”的，去 $x$ 较小的地方买。

具体地，有下列过程。

• 得到 $k$，将数组按照 $x$ 从小到大排序。

• 然后，枚举前 $i$ 个糖果的“1”要买，剩下的钱都去买“2”，得到这些结果后取最大值。

代码：

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int N=1e5+5;
struct Node{
	int x,y;
}a[N];
signed main(){
	int n,m;cin >> n >> m;
	int mn=1e18+7;
	for (int i=1;i<=n;++i) cin >> a[i].x >> a[i].y,mn=min(mn,a[i].x+a[i].y);
	sort(a+1,a+1+n,[](const Node &a,const Node &b){
		return a.x<b.x;
	});
	int ans=0,sm=0;
	for (int i=0;i<=n;++i){
		sm+=a[i].x;
		if (sm>m) break;
		ans=max(ans,i+(m-sm)/mn*2);
	}
	cout<<ans<<"\n";
	return 0;
}

后记：100+32+8+30，我的游记，省年排4。为啥这把都这么低啊，这个分不是很好打吗/yiw。