Solution CF1165F2 Microtransactions (hard version)

做本题之前建议先完成本题的简化版。

思路分析

这题 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;
}