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

· · 题解

因为没有特判，导致出现负数，导致该题挂了。。

Solution

显然有一个简单的策略：以 x+y 最小的那一个糖果为周期，不停的取。

但是还会剩下一些钱，考虑买其他糖果的 x，也不可能买到 y，因为如果买到 y 的话就不会优于买 x+y 最小的那一个糖果。

将 x 从小到大排序，再依次枚举要买多少个糖果的 x。

时间复杂度 O(n\log n)，可以通过此题。

AC code

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,x,y,t[100005],ans,minn=1e18,sum;
signed main(){
    cin>>n>>m;
    for(int i = 1;i<=n;i++) cin>>x>>y,minn=min(minn,x+y),t[i]=x;
    sort(t+1,t+1+n);
    for(int i = 1;i<=n;i++){
        if(sum<=m) ans=max(ans,(m-sum)/minn*2+i-1);//死在未判sum<=m
        sum+=t[i];
    }
    if(sum<=m) ans=max(ans,(m-sum)/minn*2+n);
    cout<<ans;
    return 0;
}