Gadgets for dollars and pounds

发表于 分类于 ，

    现在你需要买m件物品，每件物品的价格是c，种类是t。当种类为1号时，价格的单位是美元，当种类为2时，价格的单位是英镑。

    给你接下来n天的美元和英镑的汇率，$a_i$代表第i天1美元可兑换的卢布，$b_i$代表第i天1英镑可兑换的卢布。

    你现在有s卢布，问能够买至少k件物品（$k\le m$）的最少天数是多少。并构造一个包含购买物品的编号和日期的序列。

Gadgets for dollars and pounds

Created by LXC on Tue Jun 13 09:19:56 2023

https://codeforces.com/problemset/problem/609/D

ranting: 2000

tag: binary search, greedy, two pointers

problem

现在你需要买m件物品，每件物品的价格是c，种类是t。当种类为1号时，价格的单位是美元，当种类为2时，价格的单位是英镑。

给你接下来n天的美元和英镑的汇率，$a_i$代表第i天1美元可兑换的卢布，$b_i$代表第i天1英镑可兑换的卢布。

你现在有s卢布，问能够买至少k件物品（$k\le m$）的最少天数是多少。并构造一个包含购买物品的编号和日期的序列。

solution

看到最少天数，想到二分答案，并用贪心来验证答案。

对于一个指定的天数x，如果在前x天内能够买到k件物品，那么多加一天也能买到k件，显然是随着x的增长，结果由买不到k件变化到能买到k件。这其实也可看作单调非减函数。可以在这个单调函数上二分查找，找到最小的x能使得买到k件物品即可。

接下来是贪心验证能否买到k件。

对于前x天，我们分别选择美元和英镑汇率最小值，记作ma和mb，并记录这两天的日期da和db。显然买美元购买的物品要在da这样一天买最划算，英镑物品同理。
接下来我们需要从m个物品中选择k个物品，这k个物品有可能是用美元购买也有可能是用英镑购买。不妨设用美元买的物品个数为k1,设用英镑买的物品个数是k2。为了买到最便宜的货以买到更多的货，应该买k1件最便宜的美元商品，和k2件最便宜的英镑商品。我们可以枚举k1，进而得到k2 = k-k1。如果这种选购方法所花的钱不超过s，那么前x天是可以买到k件物品的。

对于贪心的实现的方法其实可以对商品排序，种类编号小的排前面，对于种类编号为1的价值降序排序，种类编号为2的升序排序。

随后便可以在这个序列上用滑动窗口算法，固定窗口大小为k，统计窗口内物品的价值，当价值不超过k便找到了一种选购方式。

code

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

struct Node {
    int id, t, c;
    Node(int id, int t, int c) : id(id), t(t), c(c) {}
    bool operator<(const Node& o) const {
        if (t != o.t) {
            return t < o.t;
        } else if (t == 1) {
            return c > o.c;
        } else {
            return c < o.c;
        }
    }
};

void sol() {
    ll n, m, k, s;
    cin >> n >> m >> k >> s;
    vector<ll> a(n), b(n);
    for (auto& i : a)
        cin >> i;
    for (auto& i : b)
        cin >> i;
    vector<Node> g;
    for (int i = 0; i < m; i++) {
        int t, c;
        cin >> t >> c;
        g.emplace_back(i + 1, t, c);
    }
    sort(g.begin(), g.end());
    // for (int i = 0; i < m; i++) {
    //     cout << g[i].id << " " << g[i].c << " " << g[i].t << "\n";
    // }
    ll l = 1, r = n + 1;
    while (l < r) {
        ll mid = l + r >> 1;
        int ok = 0;
        ll ma = *min_element(a.begin(), a.begin() + mid);
        ll mb = *min_element(b.begin(), b.begin() + mid);
        ll cnt = 0;
        for (int i = 0; i < m; i++) {
            cnt += (g[i].t == 1 ? ma : mb) * g[i].c;
            if (i >= k) {
                cnt -= (g[i - k].t == 1 ? ma : mb) * g[i - k].c;
            }
            if (i >= k - 1 && cnt <= s) {
                ok = 1;
                break;
            }
        }
        if (ok) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    if (r == n + 1) {
        cout << "-1\n";
    } else {
        cout << r << "\n";
        ll ma = *min_element(a.begin(), a.begin() + r);
        ll mb = *min_element(b.begin(), b.begin() + r);
        ll da, db;
        for (int i = 0; i < r; i++) {
            if (a[i] == ma)
                da = i + 1;
            if (b[i] == mb)
                db = i + 1;
        }
        ll cnt = 0;
        for (int i = 0; i < m; i++) {
            cnt += (g[i].t == 1 ? ma : mb) * g[i].c;
            if (i >= k) {
                cnt -= (g[i - k].t == 1 ? ma : mb) * g[i - k].c;
            }
            if (i >= k - 1 && cnt <= s) {
                for (int j = i - k + 1; j <= i; j++) {
                    cout << g[j].id << " " << (g[j].t == 1 ? da : db) << "\n";
                }
                break;
            }
        }
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}