P14635 [NOIP2025] 糖果店 / candy 题解

· · 题解

题目传送门：P14635 [NOIP2025] 糖果店 / candy

题目分析

有一个关键的结论：只有一个 y_i 会被选，并且选择序列里会有这对 x_i,y_i 漫长的交替轮回。根据贪心策略，这对 x_i+y_i 是 n 对里最小的。

证明：假如有另一个 y_j 被选了，则 x_j 肯定也被选过，同时 x_i + y_i \leqslant x_j + y_j，将这对 x_j,y_j 替换成 x_i,y_i 更优或不劣。

既然这样，除了这对 x_i,y_i 以外我们选的元素只有 O(n) 个。我们可以采取比较随便的做法。

记 x_i+y_i = K。

我们先假设 m 全用来选这对了，容易得出糖果有 2 \lfloor \dfrac{m}{K} \rfloor 颗，剩余钱数就模一下 K。

然后对于剩下的 x_j 们，先升序排序，从小到大遍历，遍历到 j 时我们计算除了 x_i,y_i 以外还恰选取了 x_1 \sim x_j 的结果（此处的下标是排序后的，所以选一个贵的糖之前肯定把便宜的都选过了）。

我们用反悔贪心的思想，如果当前 m 小于 x_j，则把之前选的 x_i,y_i 退回去，拿着要回来的钱买新的。

最后把所有时候取 \min 即可。

代码实现

复现的考场代码，应该差不多。

#include<iostream>
#include<algorithm>
using namespace std;
constexpr int N=100005;
int n,x[N],y[N],I=1,i,K;
long long m,sum,ans,cnt;
int main(){
    cin>>n>>m;
    for(i=1;i<=n;i++){
        cin>>x[i]>>y[i];
        if(x[i]+y[i]<x[I]+y[I])I=i;
    }
    K=x[I]+y[I];
    ans=sum=cnt=m/K*2;
    cnt/=2,m%=K;
    sort(x+1,x+1+n);
    for(i=1;i<=n;i++){
        while(cnt>0&&m<x[i])m+=K,cnt--,sum-=2;
        if(m<x[i])break;
        m-=x[i],sum++;
        ans=max(ans,sum);
    }
    cout<<ans;
    return 0;
}