Skip to content

S2OJ - 636. 购物

题解855 字
# 贪心 # 反悔贪心 # S2OJ # JZOJ
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#问题描述

S 城的商场中，有着琳琅满目的各种商品。一日，小 X 带着小 Y 前来购物，小 Y 一共看中了 nn 件商品，每一件商品价格为 PiP_i。小 X 现在手中共有 mm 元现金，以及 kk 张优惠券。小 X 可以在购买某件商品时，使用至多一张优惠券，若如此做，该商品的价格会下降至 QiQ_i。

小 X 希望尽可能多地满足小 Y 的愿望，所以小 X 想要知道他至多能购买多少件商品。

#输入格式

第一行包含三个整数 n,k,mn, k, m，表示商品总数，小 X 拥有的优惠券与现金总数。

接下来 nn 行每行包含两个整数 Pi,QiP_i, Q_i。

#输出格式

共一行包含一个整数，表示小 X 至多能购买的物品数。

#输入输出样例

样例输入 #1

4 1 7
3 2
2 2
8 1
4 3

样例输出 #1

3

样例解释 #1

一种最优的购买方式是购买 1,2,31, 2, 3 号物品，并用优惠券购买物品 33，总共花费为 3+2+1=63 + 2 + 1 = 6。

#数据范围

对于 100%100\% 的数据，满足 1≤k≤n≤5×1041 \leq k \leq n \leq 5 \times 10^4，1≤m≤10141 \leq m \leq 10^{14}，1≤Qi≤Pi≤1091 \leq Q_i \leq P_i \leq 10^9。

测试点编号 nn kk mm 测试点分值
11 =4=4 =1=1 =7=7 55
22 =3=3 =58=58
33 =35=35 =17=17 =9013=9013 1010
44 =125=125 =74=74 =177823513=177823513
55 =614=614 =167=167 =743819997=743819997
66 =2428=2428 =2426=2426 =2014408181=2014408181
77 =13944=13944 =13368=13368 =782324445=782324445 55
88 =49914=49914 =35877=35877 =1442873105=1442873105
99 =49899=49899 =8=8 =344155=344155 1010
1010 =50000=50000 =49999=49999 =2931491013=2931491013
1111 =49914=49914 =35877=35877 =1442873105=1442873105 55
1212 =50000=50000 =14902=14902 =230732265=230732265
1313 =5=5 =3=3 =13=13
1414 =1=1 =33=33

#思路

反悔贪心。

先选择优惠价前 kk 小的商品购买，之后再看能否使用原价比已经购买的最贵的商品的价格便宜的商品替换掉那个贵的商品（反悔操作）。

#代码

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <algorithm>
#include <queue>
#include <utility>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 50005;

int n, k;
long long m, sum;
std::pair<long long, long long> a[N];
std::priority_queue<long long, std::vector<long long>, std::greater<long long>> q;

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k >> m;

    for (int i = 1; i <= n; i++) {
        cin >> a[i].first >> a[i].second;
    }

    std::sort(a + 1, a + n + 1, [](auto a, auto b) {
        return a.second < b.second;
    });

    for (int i = 1; i <= k; i++) {
        sum += a[i].second;

        q.push(a[i].first - a[i].second);

        if (sum > m) {
            cout << i - 1 << endl;

            exit(0);
        } else if (i == n) {
            cout << n << endl;

            exit(0);
        }
    }

    std::sort(a + k + 1, a + n + 1, [](auto a, auto b) {
        return a.first < b.first;
    });

    for (int i = k + 1; i <= n; i++) {
        auto x = q.top();

        sum += a[i].first;

        if (a[i].second + x < a[i].first) {
            q.pop();

            auto y = a[i].first - a[i].second;
            q.push(y);
            sum += x - y;
        }

        if (sum > m) {
            cout << i - 1 << endl;

            exit(0);
        }
    }

    cout << n << endl;

    return 0;
}