P14635 题解

libmwlmgrimpl · 2025-11-29 18:10:45 · 题解

如果两个两个买，买奇数价偶数价之和最小的一定最优。

剩下的就只能买一个了，于是偶数价都没用了，问题变成：有一个商品 c，给定价格，价值是 2，可以买无限个；还有 n 个商品 a_i，给定价格，价值是 1 ，每个只能买一个，求 m 元钱最多买到多少价值的商品？

剩下的就是简单的贪心了。把所有 a_i 从小到大排序，维护前缀和，枚举买 1 到 n 个商品 a 时能买几个商品 c。

最重点的是判 m<sum_i 的情况。钱得够才能更新，这不是很显然嘛？但是在考场上貌似就不显然了。加上 CCF 脚造的感人大样例全 AC，想都没想就美滋滋以为自己 A 了。现在只能祈祷官方数据一样脚造了。

然后就没了。想明白之后真的没多难，代码比 club 短老多了。但我感觉这题场上难度绝对有绿，一是思考难度不亚于去年 T1，二是大样例过水导致很多错解未被 hack。

#include <bits/stdc++.h>
#define int long long
using namespace std;

int a[100005], b[100005], c[100005], sum[100005];
int n, m, ans;

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        c[i] = a[i] + b[i];
    }
    sort(c + 1, c + 1 + n);
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];
    for (int i = 0; i <= n; i++) {
        if (m >= sum[i]) ans = max(ans, i + ((m - sum[i]) / c[1]) * 2);
// 只有在总钱数足够的时候才更新
    }
    cout << ans << endl;
    return 0;
}