P14635 题解

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

剩下的就只能买一个了，于是偶数价都没用了，问题变成：有一个商品

c

，给定价格，价值是

2

，可以买无限个；还有

n

个商品

a_i

，给定价格，价值是

1

，每个只能买一个，求

m

元钱最多买到多少价值的商品？

剩下的就是简单的贪心了。把所有

a_i

从小到大排序，维护前缀和，枚举买

1

到

n

个商品

a

时能买几个商品

c

。

最重点的是判

m<sum_i

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

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

CPP

#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;
}

文章操作

相关推荐

评论

P14635 题解