简化问题

先思考简化的问题，再推广到原问题，可以根据数据特殊性质来简化。

$x_i = y_i$

买多少个都是一样的，所以直接全买最小的即可。

$x_i \geq y_i$

可以理解为“第二份降价”，那么肯定两个两个买，两个两个买谁呢？就买

x_i+y_i

最小的，买到买不起为止。
然后手上还会剩钱，由于当前的钱连最便宜的一对糖果都买不起，所以肯定只能买单个的，于是对所有

x_i

排序，从便宜到贵买，直到买不起。

正解

根据以上两份简化，可以得到：最多一种糖果买的个数 $\geq 2$ 。
先计算

d

表示最便宜一对糖的价格（即

\min_{1\leq i \leq n}{x_i+y_i}

）。

然后对

x_i

排序，从小到大买（只买一个，也就只消耗

x_i

），对于每个

k\leq[0,n]

计算已经单个买了

k

个糖果，然后全部买

d

能买多少个即可。

实现的时间复杂度为

O(n\log n)

，空间复杂度为

O(n)

，时间瓶颈在排序。

细节

如果买不起就离开，不要让你的钱变成负数。

参考代码

CPP

#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
using namespace std;
typedef long long ll;

const int N=1e5+10;
ll n,m;
ll x[N],y[N];

signed main(){
	cin>>n>>m;
	rep(i,1,n)cin>>x[i]>>y[i];
	rep(i,1,n)y[i]+=x[i];
	sort(x+1,x+1+n);

	ll d=*min_element(y+1,y+1+n);
	ll ans=0;

	rep(i,1,n){
		ans=max(ans,m/d*2+(i-1)); //已经买了 i-1 个单只糖果，剩下的钱全买成对的d
		m-=x[i];
		if(m<0)break;
	}
	if(m>=0)ans=max(ans,m/d*2+n);
	cout<<ans;
}

题解：P14635 [NOIP2025] 糖果店 / candy（民间数据）

文章操作

简化问题

$x_i = y_i$

$x_i \geq y_i$

正解

相关推荐

评论

题解：P14635 [NOIP2025] 糖果店 / candy（民间数据）

文章操作

简化问题

xi=yix_i = y_ixi​=yi​

xi≥yix_i \geq y_ixi​≥yi​

正解

相关推荐

评论

$x_i = y_i$

$x_i \geq y_i$