题解：P14635 [NOIP2025] 糖果店 / candy

· · 题解

这道题目就两个字：贪心。

显然先选 x_i + y_i 最小的糖果，但是这只是其中一部分，花在这里的钱有一部分应该在其他糖果的 x_i 上，但一定不会花到其他糖果的 y_i，每次把花在 x_i + y_i 的钱取出一部分到糖果的 x_i 身上，就可以了。

具体见代码。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 5;
int n, x[N], y[N];
ll ans, ansy, minn = 1e10, sum, m;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        cin >> x[i] >> y[i];
        //找最小的每一组糖果的价格
        if(x[i] + y[i] < minn){
            minn = x[i] + y[i];
        }
    }
    //先算当前的 ans，但不是最优的
    ans = m / minn * 2, m %= minn, ansy = ans;
    //选x[i]的时候显然要从小的买
    sort(x + 1, x + n + 1);
    for(int i = 1;i <= n;i++){
        sum += x[i];
        ll th;
        //算买价格 sum 的糖果要退回多少个 minn
        if(m >= sum) th = 0;
        else if((sum - m) % minn == 0) th = (sum - m) / minn;
        else th = (sum - m) / minn + 1;
        //更新 ans 看会不会更优 
        if(th <= ans * 2 && ans - th * 2 + i > ansy){
            ansy = ans - th * 2 + i;
        }
    }
    cout << ansy;
    return 0;
}