最近在参加计院和软院的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

1
2
3
4
5
6
7
8
9
10
11
12
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

1
2
3
4
5
6
7
8
9
input:
4 3 2 200
69 70 71 72
104 105 106 107
1 1
2 2
1 2
output:
-1

样例3

1
2
3
4
5
6
7
8
9
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之内。这样便完成了第一个输出：最少天数。下面是代码实现

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
void gadget(int n, int m, int k, int s, const vector<int>& dollar,
              const vector<int>& pound, const vector<pair<int, int>>& items) {
    // 预处理：计算每天的最小汇率
    vector<int> min_dollar(n + 1), min_pound(n + 1);
    min_dollar[1] = dollar[0];
    min_pound[1] = pound[0];
    for (int i = 2; i <= n; i++) {
      min_dollar[i] = (min_dollar[i - 1] < dollar[i - 1]) ? min_dollar[i - 1]
                                                          : dollar[i - 1];
      min_pound[i] =
          (min_pound[i - 1] < pound[i - 1]) ? min_pound[i - 1] : pound[i - 1];
    }

    int answer_day = -1;

    // 寻找最早可行的天数
    for (int day = 1; day <= n; day++) {
      vector<int> cost;
      int md = min_dollar[day];
      int mp = min_pound[day];
    // 计算每个小东西在当天的成本
      for (const auto& [type, price] : items) {
        if (type == 1)
          cost.push_back(price * md);
        else
          cost.push_back(price * mp);
      }

      sort(cost.begin(), cost.end());
      long long total = 0;
      for (int i = 0; i < k; i++) {
        total += cost[i];
      }

      if (total <= s) {
        answer_day = day;
        break;  // 找到最早可行日期，退出
      }
    }

    // 输出结果
    if (answer_day == -1) {
        cout << -1 << endl;
        return;
    }

    cout << answer_day << endl;
}

为了能够输出购买方案，我们需要在找到最早可行天数后，再次计算当天每个小东西的成本，并记录下最便宜的k个小东西的成本。因此，我们需要在上面的代码中加入一个final_cost数组来保存这些成本。然后，我们再遍历一遍小东西列表，找到对应成本的小东西，并输出购买方案。下面是补充的代码：

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
vector<int> final_cost;
final_cost = cost;
// 输出购买方案
vector<bool> used(m, false);

for (int d = 1; d <= answer_day; d++) {
    int cd = dollar[d - 1];
    int cp = pound[d - 1];

    for (int i = 0; i < m; i++) {
    if (used[i]) continue;

    const auto& [type, price] = items[i];
    int cst = (type == 1) ? price * cd : price * cp;

    // 检查这个成本是否在最便宜的k个中
    if (cst <= s) {
        cout << (i + 1) << ' ' << d << '\n';
        used[i] = true;
        s -= cst;
        // 更新final_cost，移除已使用的成本
        for (int j = 0; j < k; j++) {
        if (final_cost[j] == cst) {
            final_cost[j] = 2000000000;  // 设为很大的值
            break;
        }
        }
        sort(final_cost.begin(), final_cost.end());
    }
    }
}

这个算法的时间复杂度非常高，因为进行了多次模拟，每次模拟都需要排序，达到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
2
3
4
5
6
7
8
9
10
11
12
13
14
// 二分查找最早可行天数
int left = 1, right = n + 1;
while (left < right) {
    int mid = left + (right - left) / 2;
    if (canBuy(mid)) right = mid;
    else left = mid + 1;
}
if (left > n) {
    cout << -1 << endl;
    return;
}

int ans = left;
cout << ans << endl;

上面的canBuy(mid)函数用于判断在前mid天内是否能买到k个小东西，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
auto canBuy = [&](int day) {
    vector<int> min_cost(m);
    for (int i = 0; i < m; i++) {
        min_cost[i] = cost[i][day];
    }
    sort(min_cost.begin(), min_cost.end());
    long long total = 0;
    for (int i = 0; i < k; i++) {
        total += min_cost[i];
    }
    return total <= s;
}

为了判断某一天能否买到k个小东西，我们可以使用类似之前的方法，计算前mid天的最低汇率，然后计算每个小东西的成本，并判断前k个小东西的总成本是否在预算内。这样，我们仍然需要对汇率进行预处理，方便将成本转化成卢布进行排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> min_dollar(n + 1), min_pound(n + 1);
min_dollar[1] = dollar[0];
min_pound[1] = pound[0];
for (int i = 2; i <= n; i++) {
    min_dollar[i] = min(min_dollar[i - 1], dollar[i - 1]);
    min_pound[i] = min(min_pound[i - 1], pound[i - 1]);
}

vector<vector<ll>> cost(m, vector<ll>(n + 1));
for (int i = 0; i < m; i++) {
    for (int d = 1; d <= n; d++) {
    int rate = (items[i].first == 1) ? min_dollar[d] : min_pound[d];
    cost[i][d] = items[i].second * rate;
    }
}

这里我们对cost数组进行了升级，使得它不仅存储每个小东西在某一天的成本，还存储了在前d天内的最低成本。这样，在canBuy(mid)函数中，我们可以直接使用cost[i][mid]来获取每个小东西在前mid天内的最低成本。
为了方便地输出购买方案，我们可以构建一个item结构体，包含cost,id,buy_day等信息。然后，在找到最早可行天数后，我们可以再次计算当天每个小东西的成本，并记录下最便宜的k个小东西的成本和购买天数。最后，输出购买方案。

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
struct Item {
    ll cost;
    int id, buy_day;
    bool operator<(const Item& other) const { return cost < other.cost; }
};

// 构建一个数组存储所有小东西在最早可行天数内的成本和购买天数
vector<Item> all;
for (int d = 1; d <= ans; d++) {
    int cd = dollar[d - 1];
    int cp = pound[d - 1];
    for (int i = 0; i < m; i++) {
        const auto& [type, price] = items[i];
        ll cst = (type == 1) ? price * cd : price * cp;
        all.push_back({cst, i + 1, d});
    }
}
 
// 对所有小东西按成本排序
sort(all.begin(), all.end());

// 输出购买方案
int bought = 0; // 已购买数量
vector<bool> selected(m + 1, false); // 记录已选择的小东西
for (const auto& option : all) {
    if (bought >= k) break; // 买够k个就停止
    if (selected[option.id]) continue; // 已经买过了
    cout << option.id << ' ' << option.buy_day << '\n';
    selected[option.id] = true; // 标记为已购买
    bought++;
}

这样，我们利用二分查找提升了模拟购买的效率。但是在这个过程中，我们构建了太多的数据结构，比如结构体、数组，甚至构建了一个all数组来存储所有小东西的成本、序号和购买天数，这使得空间复杂度极高，达到了O(n*m)。而为了预处理汇率，我们构造了一个预处理矩阵，它的时间复杂度也达到了O(n*m)，并且在重构购买方案时，我们又遍历了从1到ans的所有天数，最坏情况下时间复杂度达到了O(n*m*log(n*m))。因此，这个解法在数据量较大时仍然无法通过测试点。

优化时空复杂度

首先，我们一般不希望构建一个结构体数组来存储所有数据，比如它的购买时间。实际上，所有最优的购物时间都是当天之前汇率最低的那一天，因此我们只需要记录每一天的最低汇率对应的天数即可。其次，我们不需要构建一个cost矩阵来存储每个小东西在每一天的成本。实际上，我们只需要在判断某一天是否可行时，计算当天每个小东西的成本，并进行排序即可。这样，我们可以将空间复杂度降低到O(m+n)。

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
vector<int> min_dollar(n + 1), min_pound(n + 1);  // 记录前i天的最低汇率
vector<int> best_dollar_day(n + 1), best_pound_day(n + 1);  // 记录最低汇率对应的天数

min_dollar[1] = dollar[0];
min_pound[1] = pound[0];
best_dollar_day[1] = best_pound_day[1] = 1;

for (int i = 2; i <= n; i++) {
    if (dollar[i - 1] < min_dollar[i - 1]) {
    min_dollar[i] = dollar[i - 1];
    best_dollar_day[i] = i;
    } else {
    min_dollar[i] = min_dollar[i - 1];
    best_dollar_day[i] = best_dollar_day[i - 1];
    }

    if (pound[i - 1] < min_pound[i - 1]) {
    min_pound[i] = pound[i - 1];
    best_pound_day[i] = i;
    } else {
    min_pound[i] = min_pound[i - 1];
    best_pound_day[i] = best_pound_day[i - 1];
    }
}

vector<pair<ll, int>> item_costs(m);  // 存储每个小东西在ans天的最低成本和索引

for (int i = 0; i < m; i++) {  // 在第ans天从1到m遍历所有物品
    if (items[i].first == 1) {
    ll cost = items[i].second * min_dollar[ans];  // 计算在ans天的成本
    } else {
    ll cost = items[i].second * min_pound[ans];
    }
    item_costs[i] = {cost, i + 1};
}

// 按照成本排序
sort(item_costs.begin(), item_costs.end());

// 选取前k个小东西输出购买方案
for (int i = 0; i < k; i++) {
    int item_id = item_costs[i].second;
    int item_idx = item_id - 1;
    // 确定购买的最佳天数，即为最低汇率对应的天数
    int best_day = (items[item_idx].first == 1) ? best_dollar_day[ans]
                                                : best_pound_day[ans];
    cout << item_id << ' ' << best_day << '\n';
}

为了适配这种改变，我们需要修改canBuy(day)函数，使其在计算成本时直接使用当天的最低汇率，而不是预处理矩阵。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
auto canBuy = [&](int day) {
    vector<ll> costs(m);
    for (int i = 0; i < k; i++) {
        int rate = (items[i].first == 1) ? min_dollar[day] : min_pound[day];
        costs[i] = items[i].second * rate;
    }
    sort(costs.begin(), costs.end());
    long long total = 0;
    for (int i = 0; i < k; i++) {
        total += costs[i];
    }
    return total <= s;
}

这个函数的时间复杂度为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
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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;

void gadgets(int n, int m, int k, ll s, const vector<int>& dollar,
             const vector<int>& pound, const vector<pair<int, int>>& items) {
    // 预处理汇率：计算每天的最小汇率及其对应天数
    vector<int> min_dollar(n + 1), min_pound(n + 1);
    vector<int> best_dollar_day(n + 1), best_pound_day(n + 1);
    min_dollar[1] = dollar[0];
    min_pound[1] = pound[0];
    best_dollar_day[1] = best_pound_day[1] = 1;

    for (int i = 2; i <= n; i++) {
        if (dollar[i - 1] < min_dollar[i - 1]) {
            min_dollar[i] = dollar[i - 1];
            best_dollar_day[i] = i;
        } else {
            min_dollar[i] = min_dollar[i - 1];
            best_dollar_day[i] = best_dollar_day[i - 1];
        }
        if (pound[i - 1] < min_pound[i - 1]) {
            min_pound[i] = pound[i - 1];
            best_pound_day[i] = i;
        } else {
            min_pound[i] = min_pound[i - 1];
            best_pound_day[i] = best_pound_day[i - 1];
        }
    }

    // 预处理物品：分类并按原始价格排序
    vector<pair<int, int>> d_items, p_items; // {price, original_index}
    for (int i = 0; i < m; i++) {
        if (items[i].first == 1) d_items.push_back({items[i].second, i + 1});
        else p_items.push_back({items[i].second, i + 1});
    }
    sort(d_items.begin(), d_items.end());
    sort(p_items.begin(), p_items.end());

    // 计算价格前缀和
    vector<ll> d_sum(d_items.size() + 1, 0), p_sum(p_items.size() + 1, 0);
    for (int i = 0; i < d_items.size(); i++) d_sum[i + 1] = d_sum[i] + d_items[i].first;
    for (int i = 0; i < p_items.size(); i++) p_sum[i + 1] = p_sum[i] + p_items[i].first;

    // 高效 canBuy 函数：O(K) 时间复杂度
    auto canBuy = [&](int day) {
        ll md = min_dollar[day], mp = min_pound[day];
        // 枚举美元物品买 x 个，英镑物品则买 k-x 个
        for (int x = 0; x <= k; x++) {
            int y = k - x;
            if (x <= d_items.size() && y >= 0 && y <= p_items.size()) {
                // 计算总卢布开销，注意强制转型 ll 防止溢出
                if (d_sum[x] * md + p_sum[y] * mp <= s) return true;
            }
        }
        return false;
    };

    // 二分查找天数
    int left = 1, right = n + 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canBuy(mid)) right = mid;
        else left = mid + 1;
    }

    if (left > n) {
        cout << -1 << endl;
        return;
    }

    // 输出结果与购买方案
    int ans = left;
    cout << ans << endl;

    // 寻找在 ans 天时，哪种购买组合方案（美元买 x 个）是可行的
    int best_x = -1;
    for (int x = 0; x <= k; x++) {
        int y = k - x;
        if (x <= d_items.size() && y >= 0 && y <= p_items.size()) {
            if (d_sum[x] * (ll)min_dollar[ans] + p_sum[y] * (ll)min_pound[ans] <= s) {
                best_x = x;
                break;
            }
        }
    }

    // 输出美元物品方案
    for (int i = 0; i < best_x; i++)
        cout << d_items[i].second << " " << best_dollar_day[ans] << "\n";
    // 输出英镑物品方案
    for (int i = 0; i < k - best_x; i++)
        cout << p_items[i].second << " " << best_pound_day[ans] << "\n";
}

总结

做完这道题，我感到以往对二分查找的理解还不够深入。实际上，我是通过与AI对话才想到原来可以使用二分查找来优化模拟过程，并用canBuy函数作为最优化判据。以前当我想到利用二分查找时，一般是直接对答案进行二分，或者是题目中明显已经排序好的的某个量进行二分，而这道题的思路则是对时间进行二分，因为时间实际上也是线性的，这一点相对隐蔽。
其次，前缀和的使用也让我受益匪浅。通过预处理前缀和，我们可以在canBuy函数中快速计算出购买x个美元物品和k-x个英镑物品的总成本，而不需要每次都重新计算和排序，这大大提升了效率。
另外，这道题也让我感受到时间和空间复杂度的重要性，这时以前做黄题很少感受到的一点。

2026年1月26日。