~/posts/Gadgets.md

记一道二分算法题:CF609D

2026-01-26 11 分钟 · 5269 字11 min · 5269 words notes / algorithm / binary-search algorithmnotesbinary-search
目录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

text
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

text
input:
4 3 2 200
69 70 71 72
104 105 106 107
1 1
2 2
1 2
output:
-1

样例3

text
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之内。这样便完成了第一个输出:最少天数。下面是代码实现

c++
 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数组来保存这些成本。然后,我们再遍历一遍小东西列表,找到对应成本的小东西,并输出购买方案。下面是补充的代码:

c++
 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)。

c++
 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个小东西,代码如下:

c++
 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个小东西的总成本是否在预算内。这样,我们仍然需要对汇率进行预处理,方便将成本转化成卢布进行排序。

c++
 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个小东西的成本和购买天数。最后,输出购买方案。

c++
 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)。

c++
 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)函数,使其在计算成本时直接使用当天的最低汇率,而不是预处理矩阵。代码如下:

c++
 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] 来计算总成本,而不需要每次都重新计算。

完整代码

c++
 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

滚动到这里时加载评论…Comments load when you scroll here…