记一道二分算法题:CF609D
目录Contents
最近在参加计院和软院的WinterCode比赛,其中有一道题为CF609D。解题过程挺挣扎的,也是第一次做绿题,记录一下想的过程。 这里方便阅读,贴一下题目描述:
Nura想要购买k样小东西,但她手里只有s卢布。然而,商店里只收美元或英镑。货币种类和以该货币计价的价格都不会改变。
Nura可以在n天里购买小东西。每一天,她将知道美元和英镑的汇率,所以她可以知道她能用手中的卢布兑换多少美元和英镑。
对于从1到n的每一天,Nura可以通过汇率购买小东西。在一天内,她可以选择购买任何她想买的东西,但是每个东西在这n天里只能购买一次。
请你帮Nura找到一个购买方案,使她能用最少的天数买到k样小东西。Nura总是用卢布支付,而卢布是根据汇率在当天兑换成美元或英镑的。Nura无法购买美元或英镑,她的手里只有卢布。小东西会根据他们出现的次序编号为1到m。
第一行包含四个整数n,m,k和s(1 ≤ n, m, k ≤ 10^5,1 ≤ s ≤ 10^9)。——表示天数,小东西数量,想买的小东西数量和手中的卢布数量。
第二行包含n个整数a1, a2, ..., an(1 ≤ ai ≤ 10^6),——表示第i天美元的汇率。
第三行包含n个整数b1, b2, ..., bn(1 ≤ bi ≤ 10^6),——表示第i天英镑的汇率。
下面的m行,每行包含两个整数ti和ci(ti ∈ {1, 2},1 ≤ ci ≤ 10^6),——表示第i样小东西的货币种类和价格。ti = 1表示以美元计价,ti = 2表示以英镑计价。
输出一个整数x——表示Nura能在前x天内买到k样小东西的最小值。如果Nura无法买到k样小东西,输出-1。
接下来输出k行,每行包含两个整数di和pi——表示Nura在第pi天购买第di样小东西。如果有多种方案,输出任意一种。
样例:
样例1
input:
5 4 2 2
1 2 3 2 1
3 2 1 2 3
1 1
2 1
1 2
2 2
output:
3
1 1
2 3样例2
input:
4 3 2 200
69 70 71 72
104 105 106 107
1 1
2 2
1 2
output:
-1样例3
input:
4 3 1 1000000000
900000 910000 940000 990000
990000 999000 999900 999990
1 87654
2 76543
1 65432
output:
-1直接模拟
最直接的想法是直接模拟每一天的购买过程,直到买够k个东西为止。怎样买才能使得买的东西尽可能多呢?需要两个条件:对于前i天,我们需要在汇率最低的那一天购买对应货币的小东西;其次,我们需要优先购买价格最低的小东西。因此,我们需要构建两个数组,比如min_dollar和min_pound,分别记录前i天美元和英镑的最低汇率及其对应的天数。然后,进行每一天的模拟。在一天中,构建一个数组cost来计算每天各种小东西按卢布计算的价格(即cost[i] = min_dollar[day] * price或者cost[i] = min_pound[day] * price)并进行排序,然后判断数组前k个小东西的总价是否在预算s之内。这样便完成了第一个输出:最少天数。下面是代码实现
1void gadget(int n, int m, int k, int s, const vector<int>& dollar,
2 const vector<int>& pound, const vector<pair<int, int>>& items) {
3 // 预处理:计算每天的最小汇率
4 vector<int> min_dollar(n + 1), min_pound(n + 1);
5 min_dollar[1] = dollar[0];
6 min_pound[1] = pound[0];
7 for (int i = 2; i <= n; i++) {
8 min_dollar[i] = (min_dollar[i - 1] < dollar[i - 1]) ? min_dollar[i - 1]
9 : dollar[i - 1];
10 min_pound[i] =
11 (min_pound[i - 1] < pound[i - 1]) ? min_pound[i - 1] : pound[i - 1];
12 }
13
14 int answer_day = -1;
15
16 // 寻找最早可行的天数
17 for (int day = 1; day <= n; day++) {
18 vector<int> cost;
19 int md = min_dollar[day];
20 int mp = min_pound[day];
21 // 计算每个小东西在当天的成本
22 for (const auto& [type, price] : items) {
23 if (type == 1)
24 cost.push_back(price * md);
25 else
26 cost.push_back(price * mp);
27 }
28
29 sort(cost.begin(), cost.end());
30 long long total = 0;
31 for (int i = 0; i < k; i++) {
32 total += cost[i];
33 }
34
35 if (total <= s) {
36 answer_day = day;
37 break; // 找到最早可行日期,退出
38 }
39 }
40
41 // 输出结果
42 if (answer_day == -1) {
43 cout << -1 << endl;
44 return;
45 }
46
47 cout << answer_day << endl;
48}为了能够输出购买方案,我们需要在找到最早可行天数后,再次计算当天每个小东西的成本,并记录下最便宜的k个小东西的成本。因此,我们需要在上面的代码中加入一个final_cost数组来保存这些成本。然后,我们再遍历一遍小东西列表,找到对应成本的小东西,并输出购买方案。下面是补充的代码:
1vector<int> final_cost;
2final_cost = cost;
3// 输出购买方案
4vector<bool> used(m, false);
5
6for (int d = 1; d <= answer_day; d++) {
7 int cd = dollar[d - 1];
8 int cp = pound[d - 1];
9
10 for (int i = 0; i < m; i++) {
11 if (used[i]) continue;
12
13 const auto& [type, price] = items[i];
14 int cst = (type == 1) ? price * cd : price * cp;
15
16 // 检查这个成本是否在最便宜的k个中
17 if (cst <= s) {
18 cout << (i + 1) << ' ' << d << '\n';
19 used[i] = true;
20 s -= cst;
21 // 更新final_cost,移除已使用的成本
22 for (int j = 0; j < k; j++) {
23 if (final_cost[j] == cst) {
24 final_cost[j] = 2000000000; // 设为很大的值
25 break;
26 }
27 }
28 sort(final_cost.begin(), final_cost.end());
29 }
30 }
31}这个算法的时间复杂度非常高,因为进行了多次模拟,每次模拟都需要排序,达到O(n*m*log m + n*m*k*log k),难以通过测试点。而且,因为ai*ci可能达到10^12,需要使用long long类型存储成本。这样空间复杂度也会很高。
二分优化
在上面的做法中,我们选择逐天模拟,这在天数较多的情况下效率很低。我们可以使用二分查找来优化这个过程。具体来说,我们可以对天数进行二分查找,判断在中间天数mid内是否能买到k个小东西。如果能买到,则尝试缩小天数范围;如果不能买到,则增加天数范围。我们希望可以将时间复杂度降低到O(m*log m+n+log n*m)。
1// 二分查找最早可行天数
2int left = 1, right = n + 1;
3while (left < right) {
4 int mid = left + (right - left) / 2;
5 if (canBuy(mid)) right = mid;
6 else left = mid + 1;
7}
8if (left > n) {
9 cout << -1 << endl;
10 return;
11}
12
13int ans = left;
14cout << ans << endl;上面的canBuy(mid)函数用于判断在前mid天内是否能买到k个小东西,代码如下:
1auto canBuy = [&](int day) {
2 vector<int> min_cost(m);
3 for (int i = 0; i < m; i++) {
4 min_cost[i] = cost[i][day];
5 }
6 sort(min_cost.begin(), min_cost.end());
7 long long total = 0;
8 for (int i = 0; i < k; i++) {
9 total += min_cost[i];
10 }
11 return total <= s;
12}为了判断某一天能否买到k个小东西,我们可以使用类似之前的方法,计算前mid天的最低汇率,然后计算每个小东西的成本,并判断前k个小东西的总成本是否在预算内。这样,我们仍然需要对汇率进行预处理,方便将成本转化成卢布进行排序。
1vector<int> min_dollar(n + 1), min_pound(n + 1);
2min_dollar[1] = dollar[0];
3min_pound[1] = pound[0];
4for (int i = 2; i <= n; i++) {
5 min_dollar[i] = min(min_dollar[i - 1], dollar[i - 1]);
6 min_pound[i] = min(min_pound[i - 1], pound[i - 1]);
7}
8
9vector<vector<ll>> cost(m, vector<ll>(n + 1));
10for (int i = 0; i < m; i++) {
11 for (int d = 1; d <= n; d++) {
12 int rate = (items[i].first == 1) ? min_dollar[d] : min_pound[d];
13 cost[i][d] = items[i].second * rate;
14 }
15}这里我们对cost数组进行了升级,使得它不仅存储每个小东西在某一天的成本,还存储了在前d天内的最低成本。这样,在canBuy(mid)函数中,我们可以直接使用cost[i][mid]来获取每个小东西在前mid天内的最低成本。
为了方便地输出购买方案,我们可以构建一个item结构体,包含cost,id,buy_day等信息。然后,在找到最早可行天数后,我们可以再次计算当天每个小东西的成本,并记录下最便宜的k个小东西的成本和购买天数。最后,输出购买方案。
1struct Item {
2 ll cost;
3 int id, buy_day;
4 bool operator<(const Item& other) const { return cost < other.cost; }
5};
6
7// 构建一个数组存储所有小东西在最早可行天数内的成本和购买天数
8vector<Item> all;
9for (int d = 1; d <= ans; d++) {
10 int cd = dollar[d - 1];
11 int cp = pound[d - 1];
12 for (int i = 0; i < m; i++) {
13 const auto& [type, price] = items[i];
14 ll cst = (type == 1) ? price * cd : price * cp;
15 all.push_back({cst, i + 1, d});
16 }
17}
18
19// 对所有小东西按成本排序
20sort(all.begin(), all.end());
21
22// 输出购买方案
23int bought = 0; // 已购买数量
24vector<bool> selected(m + 1, false); // 记录已选择的小东西
25for (const auto& option : all) {
26 if (bought >= k) break; // 买够k个就停止
27 if (selected[option.id]) continue; // 已经买过了
28 cout << option.id << ' ' << option.buy_day << '\n';
29 selected[option.id] = true; // 标记为已购买
30 bought++;
31}这样,我们利用二分查找提升了模拟购买的效率。但是在这个过程中,我们构建了太多的数据结构,比如结构体、数组,甚至构建了一个all数组来存储所有小东西的成本、序号和购买天数,这使得空间复杂度极高,达到了O(n*m)。而为了预处理汇率,我们构造了一个预处理矩阵,它的时间复杂度也达到了O(n*m),并且在重构购买方案时,我们又遍历了从1到ans的所有天数,最坏情况下时间复杂度达到了O(n*m*log(n*m))。因此,这个解法在数据量较大时仍然无法通过测试点。
优化时空复杂度
首先,我们一般不希望构建一个结构体数组来存储所有数据,比如它的购买时间。实际上,所有最优的购物时间都是当天之前汇率最低的那一天,因此我们只需要记录每一天的最低汇率对应的天数即可。其次,我们不需要构建一个cost矩阵来存储每个小东西在每一天的成本。实际上,我们只需要在判断某一天是否可行时,计算当天每个小东西的成本,并进行排序即可。这样,我们可以将空间复杂度降低到O(m+n)。
1vector<int> min_dollar(n + 1), min_pound(n + 1); // 记录前i天的最低汇率
2vector<int> best_dollar_day(n + 1), best_pound_day(n + 1); // 记录最低汇率对应的天数
3
4min_dollar[1] = dollar[0];
5min_pound[1] = pound[0];
6best_dollar_day[1] = best_pound_day[1] = 1;
7
8for (int i = 2; i <= n; i++) {
9 if (dollar[i - 1] < min_dollar[i - 1]) {
10 min_dollar[i] = dollar[i - 1];
11 best_dollar_day[i] = i;
12 } else {
13 min_dollar[i] = min_dollar[i - 1];
14 best_dollar_day[i] = best_dollar_day[i - 1];
15 }
16
17 if (pound[i - 1] < min_pound[i - 1]) {
18 min_pound[i] = pound[i - 1];
19 best_pound_day[i] = i;
20 } else {
21 min_pound[i] = min_pound[i - 1];
22 best_pound_day[i] = best_pound_day[i - 1];
23 }
24}
25
26vector<pair<ll, int>> item_costs(m); // 存储每个小东西在ans天的最低成本和索引
27
28for (int i = 0; i < m; i++) { // 在第ans天从1到m遍历所有物品
29 if (items[i].first == 1) {
30 ll cost = items[i].second * min_dollar[ans]; // 计算在ans天的成本
31 } else {
32 ll cost = items[i].second * min_pound[ans];
33 }
34 item_costs[i] = {cost, i + 1};
35}
36
37// 按照成本排序
38sort(item_costs.begin(), item_costs.end());
39
40// 选取前k个小东西输出购买方案
41for (int i = 0; i < k; i++) {
42 int item_id = item_costs[i].second;
43 int item_idx = item_id - 1;
44 // 确定购买的最佳天数,即为最低汇率对应的天数
45 int best_day = (items[item_idx].first == 1) ? best_dollar_day[ans]
46 : best_pound_day[ans];
47 cout << item_id << ' ' << best_day << '\n';
48}为了适配这种改变,我们需要修改canBuy(day)函数,使其在计算成本时直接使用当天的最低汇率,而不是预处理矩阵。代码如下:
1auto canBuy = [&](int day) {
2 vector<ll> costs(m);
3 for (int i = 0; i < k; i++) {
4 int rate = (items[i].first == 1) ? min_dollar[day] : min_pound[day];
5 costs[i] = items[i].second * rate;
6 }
7 sort(costs.begin(), costs.end());
8 long long total = 0;
9 for (int i = 0; i < k; i++) {
10 total += costs[i];
11 }
12 return total <= s;
13}这个函数的时间复杂度为O(m log m),因为我们需要对成本进行排序。整体时间复杂度为O(m log m * log n + n + m log m),空间复杂度为O(m + n),这样就可以通过所有测试点了。
进一步优化canBuy函数
虽然前面的二分查找已经大大提升了效率,但在canBuy函数内部,我们仍然在重复做两件低效的事情:
- 重复分类与转换:每次调用
canBuy都要遍历m个物品计算成本。 - 重复排序:每次二分都要对
m个成本进行O(m log m)的排序。
我们观察到这个事实:物品的原始价格是不变的。无论汇率如何变化,同一货币计价的物品,其卢布价格的相对顺序永远不变(即:原价便宜的,换算后依然便宜)。因此,我们可以:
- 预先分类与排序:在二分查找之前,将美元和英镑物品分开,并分别按原价从小到大排序。
- 利用前缀和:预处理出两类物品价格的前缀和。
- 线性枚举:在
canBuy中,我们只需要枚举购买多少个美元物品(假设为x个),剩下的k-x个必然是买最便宜的英镑物品。这样canBuy的复杂度就从O(m log m)降到了O(k)。
所谓前缀和,就是对于一个排序后的价格数组 prices,我们构建一个前缀和数组 prefix_sum,其中 prefix_sum[i] 表示购买前 i 个物品的总价。这样,在 canBuy 中,我们可以直接通过 prefix_sum[x] 和 prefix_sum[k-x] 来计算总成本,而不需要每次都重新计算。
完整代码
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6using ll = long long;
7
8void gadgets(int n, int m, int k, ll s, const vector<int>& dollar,
9 const vector<int>& pound, const vector<pair<int, int>>& items) {
10 // 预处理汇率:计算每天的最小汇率及其对应天数
11 vector<int> min_dollar(n + 1), min_pound(n + 1);
12 vector<int> best_dollar_day(n + 1), best_pound_day(n + 1);
13 min_dollar[1] = dollar[0];
14 min_pound[1] = pound[0];
15 best_dollar_day[1] = best_pound_day[1] = 1;
16
17 for (int i = 2; i <= n; i++) {
18 if (dollar[i - 1] < min_dollar[i - 1]) {
19 min_dollar[i] = dollar[i - 1];
20 best_dollar_day[i] = i;
21 } else {
22 min_dollar[i] = min_dollar[i - 1];
23 best_dollar_day[i] = best_dollar_day[i - 1];
24 }
25 if (pound[i - 1] < min_pound[i - 1]) {
26 min_pound[i] = pound[i - 1];
27 best_pound_day[i] = i;
28 } else {
29 min_pound[i] = min_pound[i - 1];
30 best_pound_day[i] = best_pound_day[i - 1];
31 }
32 }
33
34 // 预处理物品:分类并按原始价格排序
35 vector<pair<int, int>> d_items, p_items; // {price, original_index}
36 for (int i = 0; i < m; i++) {
37 if (items[i].first == 1) d_items.push_back({items[i].second, i + 1});
38 else p_items.push_back({items[i].second, i + 1});
39 }
40 sort(d_items.begin(), d_items.end());
41 sort(p_items.begin(), p_items.end());
42
43 // 计算价格前缀和
44 vector<ll> d_sum(d_items.size() + 1, 0), p_sum(p_items.size() + 1, 0);
45 for (int i = 0; i < d_items.size(); i++) d_sum[i + 1] = d_sum[i] + d_items[i].first;
46 for (int i = 0; i < p_items.size(); i++) p_sum[i + 1] = p_sum[i] + p_items[i].first;
47
48 // 高效 canBuy 函数:O(K) 时间复杂度
49 auto canBuy = [&](int day) {
50 ll md = min_dollar[day], mp = min_pound[day];
51 // 枚举美元物品买 x 个,英镑物品则买 k-x 个
52 for (int x = 0; x <= k; x++) {
53 int y = k - x;
54 if (x <= d_items.size() && y >= 0 && y <= p_items.size()) {
55 // 计算总卢布开销,注意强制转型 ll 防止溢出
56 if (d_sum[x] * md + p_sum[y] * mp <= s) return true;
57 }
58 }
59 return false;
60 };
61
62 // 二分查找天数
63 int left = 1, right = n + 1;
64 while (left < right) {
65 int mid = left + (right - left) / 2;
66 if (canBuy(mid)) right = mid;
67 else left = mid + 1;
68 }
69
70 if (left > n) {
71 cout << -1 << endl;
72 return;
73 }
74
75 // 输出结果与购买方案
76 int ans = left;
77 cout << ans << endl;
78
79 // 寻找在 ans 天时,哪种购买组合方案(美元买 x 个)是可行的
80 int best_x = -1;
81 for (int x = 0; x <= k; x++) {
82 int y = k - x;
83 if (x <= d_items.size() && y >= 0 && y <= p_items.size()) {
84 if (d_sum[x] * (ll)min_dollar[ans] + p_sum[y] * (ll)min_pound[ans] <= s) {
85 best_x = x;
86 break;
87 }
88 }
89 }
90
91 // 输出美元物品方案
92 for (int i = 0; i < best_x; i++)
93 cout << d_items[i].second << " " << best_dollar_day[ans] << "\n";
94 // 输出英镑物品方案
95 for (int i = 0; i < k - best_x; i++)
96 cout << p_items[i].second << " " << best_pound_day[ans] << "\n";
97}总结
做完这道题,我感到以往对二分查找的理解还不够深入。实际上,我是通过与AI对话才想到原来可以使用二分查找来优化模拟过程,并用canBuy函数作为最优化判据。以前当我想到利用二分查找时,一般是直接对答案进行二分,或者是题目中明显已经排序好的的某个量进行二分,而这道题的思路则是对时间进行二分,因为时间实际上也是线性的,这一点相对隐蔽。
其次,前缀和的使用也让我受益匪浅。通过预处理前缀和,我们可以在canBuy函数中快速计算出购买x个美元物品和k-x个英镑物品的总成本,而不需要每次都重新计算和排序,这大大提升了效率。
另外,这道题也让我感受到时间和空间复杂度的重要性,这时以前做黄题很少感受到的一点。
2026年1月26日。
gitalk --repo Huaji-tye2007/MyBlog-Comments