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

Kei__ · 2025-11-29 14:05:53 · 题解

简单贪心，感觉比今年的提高组签到还简单。

本题可以转换成 01 背包与完全背包的混合，但数据范围显然不能 dp，所以需要贪心。

对权重排序，第一次 x_i 只能拿一次，贡献为一，x_i+y_i 两个一块拿可以无数次，贡献为二。找到两个一块的最小权重，无脑刷，刷的次数可以用除法算出来。如果发现少拿一个 x_i 可以再拼一次，那就拼，对只能拿一次的 x_i 做个反贪即可。

参考代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int a[N][2]; 
priority_queue< pair<int , int > , vector< pair<int , int> > , greater< pair<int , int> > >q;
signed main() {
    ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
    int n , m , ans = 0;
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i ++) {
        cin >> a[i][0] >> a[i][1];
        q.push({a[i][0] + a[i][0] , 0}); // 统一贡献，方便排序
        q.push({a[i][0] + a[i][1] , 1});
    }
    int ls = 0;
    while(m > 0) {
        if(q.empty()) break;
        pair<int , int > now = q.top();
        q.pop();
        int w = now.first , j = now.second;
        if(j < 1) w >>= 1; // 实际产生的贡献
        if(m < w) continue;
        if(j < 1) {
            ans ++;
            ls = w;
            m -= w;
        }  else {
            int v = m / w;
            if(((m + ls) / w) > v) { // 反悔
                m += ls;
                ans --;
                v = m / w;
            }
            m -= v * w;
            ans += v * 2;
        }
    }
    cout << ans;
    return 0;
}