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

· · 题解

呜呜呜，没过线没法打，幸好能补题。

显然，对于第 i 种糖果，每两颗糖果的花费为 x_i + y_i 元，为了最大化糖果数量，我们应该优先选择平均价格最低的购买方式（又名平均数贪心）。

我们找出所有糖果中 x_i + y_i 的最小值，这是购买两颗糖果的最小成本，然后用总钱数 m 除以最小双颗成本，得到可以购买的双颗数量，乘以 2 得到基础糖果数量 ，而且可能还有剩余的钱可以购买单颗糖果。我们需要检查是否能用剩余的钱购买额外的单颗糖果。

最后遍历排序后的糖果，尝试用剩余的钱购买额外的单颗糖果，更新出最大答案。

时间很明显是能过得的。

代码实现

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
struct node {
    int x, y;
}a[N];
int n, m, ans, minn = 0x3f3f3f3f3f3f3f3f;
inline bool cmp(node a, node b){
    return a.x < b.x;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i].x >> a[i].y;
    }
    for(int i = 1; i <= n; i++){
        minn = min(minn, a[i].x + a[i].y);
    }
    sort(a + 1, a + n + 1, cmp);
    ans = 2 * (m / minn);
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        cnt += a[i].x;
        if(cnt > m) break;
        ans = max(ans, 2 * ((m - cnt) / minn) + i);
    }
    cout << ans;
    return 0;
}

祝大家都能进省选，不进也可以加人品！