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

· · 题解

简化问题

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

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)，时间瓶颈在排序。
::::warning[细节]{open} 如果买不起就离开，不要让你的钱变成负数。
::::

::::success[参考代码]

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

::::