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

· · 题解

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

思路

考虑贪心。

我们知道，当存在一种糖果会被购买超过两颗时，那么为了使花费最小（或者说买的糖果最多），肯定要选择 x_i+y_i 最小的一种来买，其他糖果只需考虑是否要买第一颗即可。

那么我们又不难发现，当我们确实需要选择几种糖果并只买第一颗时，为了达到最优，一定要选择 x_i 最小的几种。

实现

可以先找出 x_i+y_i 的最小值 (x_i+y_i)_{min}，并将所有的 x_i 进行升序排序，再算出此时 x 的前缀和 s，最后枚举出只买前 i 种糖果的第一颗的 i + 1 种情况中，\left\lfloor\frac{m-s_i}{(x_i+y_i)_{min}}\right\rfloor\times2+i 的最大值即可。

代码

时间复杂度：O(nlogn)

#include<bits/stdc++.h>
#define int long long
//#define int __int128
using namespace std;
int n, m; 
int x[100010], y[100010];
int mn; //表示最小的 x_i + y_i 
int s; //表示 x 的前缀和 
int ans; //答案 
signed main() {
    //freopen("candy.in", "r", stdin);
    //freopen("candy.out", "w", stdout);
    cin >> n >> m;
    mn = 10000000000;
    for(int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
        mn = min(mn, x[i] + y[i]);
    } 
    sort(x + 1, x + n + 1);
    for(int i = 0; i <= n; i++) {
        s += x[i];
        if(s > m) break;
        ans = max(ans, (m - s) / mn * 2 + i);
    }
    cout << ans << endl;
    return 0;
}