[NOIP2025] 糖果店 题解

算法:贪心
分析:
考虑如果一个东西选好几次那这个东西的 x+y 一定最小，不然替换成最小的一定更优。
其他肯定选 x 最小的，枚举选到哪一个，剩下用最小的 x+y 补齐即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll max_n = 1e5 + 1,inf = 1e18;
ll n,m,min_candy_sum = inf,ans = 0,s;
pair<ll ,ll>candy_arr[max_n];
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    ll x,y;
    for(ll i = 1;i <= n ;i++){
        cin >> x >> y;
        candy_arr[i] = {x,y};
        min_candy_sum = min(min_candy_sum ,x + y);
    }
    sort(candy_arr + 1 , candy_arr + n + 1);
    ans = (m/min_candy_sum ) * 2;
    s = 0;
    for(int i = 1; i <= n ;i++){
        s += candy_arr[i].first;
        if(m >= s) ans = max(ans,((m-s)/min_candy_sum ) * 2 + i);
    }
    cout << ans;
}