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

· · 题解

P14635 [NOIP2025] 糖果店 / candy题解

反悔贪心?，手玩样例可以发现：
1.偶数次取可以看作每次取的贡献是 2。
2.单 x 只能取一次。x+y 可以取不限次。
3.（充分发挥人类智慧和眼力）取最便宜的 x+y 一定是优的。
4.想想背包与性价比贪心的区别，发现取 x+y 会造成浪费，然后发现可以先取单 x，然后删掉最贵的，换钱取 x+y，相当于减一加二。
5.于是发现可以贪心优先取单 x 直到遇到 x+y 再反悔。

code：

#include<bits/stdc++.h>
#define int long long
using namespace std;const int N=1e5+5,inf=1e18;int i,n,m,a[N],b,ab=inf,r;
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);freopen("candy.in","r",stdin);freopen("candy.out","w",stdout);
    for(cin>>n>>m,i=1;i<=n;ab=min(ab,a[i]+b),i++)cin>>a[i]>>b;
    sort(a+1,a+1+n);for(r=(m/ab)*2,b=a[1],i=1;i<=n and m>=b;i++,b+=a[i])r=max(r,i+((m-b)/ab)*2);
    return cout<<r,0;
}