做本题之前建议先完成本题的简化版。
思路分析
这题 hard version 的主要思想与 easy version 相同。我们唯一应替换的是搜索的方式。用二分搜索替换线性搜索可以将时间复杂度从 O(n^2) 降低到 O(n \log n)。
很明显,我们可以在此处应用二分搜索,因为如果我们可以在 d 这天订购所有微交易,那么我们就可以在 d+1 天的所有订单中订购所有微交易(即使使用 d 天的答案,也可以在 d+1 的日子不做任何交易)。
代码:
本题:
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> k;
vector<pair<int, int>> q(200001);
bool can(int day) {
vector<int> lst(n, -1);
for (int i = 0; i < m; ++i) {
if (q[i].first <= day) {
lst[q[i].second] = max(lst[q[i].second], q[i].first);
}
}
vector<vector<int>> off(200001);
for (int i = 0; i < n; ++i) {
if (lst[i] != -1) {
off[lst[i]].push_back(i);
}
}
vector<int> need = k;
int cur_money = 0;
for (int i = 0; i <= day; ++i) {
++cur_money;
if (i > 200000) continue;
for (auto it : off[i]) {
if (cur_money >= need[it]) {
cur_money -= need[it];
need[it] = 0;
} else {
need[it] -= cur_money;
cur_money = 0;
break;
}
}
}
return accumulate(need.begin(), need.end(), 0) * 2 <= cur_money;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin >> n >> m;
k = vector<int>(n);
for (int i = 0; i < n; ++i) {
cin >> k[i];
}
for (int i = 0; i < m; ++i) {
cin >> q[i].first >> q[i].second;
--q[i].first;
--q[i].second;
}
int l = 0, r = 400000;
while (r - l > 1) {
int mid = (l + r) >> 1;
if (can(mid)) r = mid;
else l = mid;
}
for (int i = l; i <= r; ++i) {
if (can(i)) {
cout << i + 1 << endl;
return 0;
}
}
assert(false);
return 0;
}
在此基础上稍作修改即可完成简化版题目:
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> k;
vector<pair<int, int>> q(1001);
bool can(int day) {
vector<int> lst(n, -1);
for (int i = 0; i < m; ++i) {
if (q[i].first <= day) {
lst[q[i].second] = max(lst[q[i].second], q[i].first);
}
}
vector<vector<int>> off(1001);
for (int i = 0; i < n; ++i) {
if (lst[i] != -1) {
off[lst[i]].push_back(i);
}
}
vector<int> need = k;
int cur_money = 0;
for (int i = 0; i <= day; ++i) {
++cur_money;
if (i > 1000) continue;
for (auto it : off[i]) {
if (cur_money >= need[it]) {
cur_money -= need[it];
need[it] = 0;
} else {
need[it] -= cur_money;
cur_money = 0;
break;
}
}
}
return accumulate(need.begin(), need.end(), 0) * 2 <= cur_money;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin >> n >> m;
k = vector<int>(n);
for (int i = 0; i < n; ++i) {
cin >> k[i];
}
for (int i = 0; i < m; ++i) {
cin >> q[i].first >> q[i].second;
--q[i].first;
--q[i].second;
}
for (int l = 0; l <= 2000; ++l) {
if (can(l)) {
cout << l + 1 << endl;
return 0;
}
}
assert(false);
return 0;
}
0 Comments