Editorial - Phân công nhiệm vụ

Ý tưởng chính

Mỗi nhiệm vụ ~i~ có thưởng:

~500x_i + 2y_i~

Máy ~j~ có thể nhận nhiệm vụ ~i~ nếu:

• ~x_i \le T_j~
• ~y_i \le D_j~

Mỗi máy nhận nhiều nhất một nhiệm vụ, mỗi nhiệm vụ cũng chỉ dùng nhiều nhất một lần.

Ta cần chọn ghép cặp máy - nhiệm vụ sao cho tổng thưởng lớn nhất.

Nhận xét quan trọng

Hệ số của ~x_i~ là ~500~, còn hệ số của ~y_i~ chỉ là ~2~.
Vì vậy khi so sánh hai nhiệm vụ có cùng điều kiện độ khó đã thỏa mãn, ta luôn ưu tiên nhiệm vụ có ~x_i~ lớn hơn trước. Nếu ~x_i~ bằng nhau thì mới ưu tiên ~y_i~ lớn hơn.

Điều này gợi ý một chiến lược tham lam:

1. Sắp xếp các nhiệm vụ theo ~y_i~ tăng dần, nếu bằng nhau thì theo ~x_i~ tăng dần.
2. Sắp xếp các máy theo ~D_j~ tăng dần, nếu bằng nhau thì theo ~T_j~ tăng dần.
3. Duyệt các máy theo thứ tự độ khó tăng dần.
   • Với máy hiện tại, đưa vào tập chọn tất cả các nhiệm vụ có ~y_i \le D_j~.
   • Trong số các nhiệm vụ đó, chỉ những nhiệm vụ có ~x_i \le T_j~ mới có thể giao cho máy.
   • Ta chọn nhiệm vụ có ~x_i~ lớn nhất không vượt quá ~T_j~.

Tại sao chọn như vậy là đúng?

• Ta đang xét các máy theo ~D_j~ tăng dần, nên khi đến máy hiện tại, mọi nhiệm vụ trong tập đều đã đủ điều kiện độ khó.
• Máy hiện tại có giới hạn thời gian ~T_j~. Nếu bỏ qua một nhiệm vụ có ~x~ lớn hơn để lấy một nhiệm vụ có ~x~ nhỏ hơn, thì giá trị thưởng sẽ không tốt hơn.
• Việc chọn nhiệm vụ có ~x~ lớn nhất khả thi cho máy hiện tại cũng là cách để dành các nhiệm vụ nhỏ hơn cho những máy yếu hơn về thời gian ở phía sau.

Cấu trúc dữ liệu

Ta dùng một multiset<pair<int,int>> để lưu các nhiệm vụ đã thỏa điều kiện độ khó của máy hiện tại.

Mỗi phần tử là:

~(x_i, y_i)~

Khi xử lí máy ~(T_j, D_j)~:

• thêm vào multiset mọi nhiệm vụ có ~y_i \le D_j~
• dùng upper_bound((T_j, D_j)) để tìm nhiệm vụ có cặp ~(\,x_i, y_i\,)~ lớn nhất mà vẫn không vượt quá giới hạn thời gian của máy
• nếu tồn tại, lấy nhiệm vụ đó, cộng thưởng và xóa khỏi multiset

Độ phức tạp

• Sắp xếp nhiệm vụ: ~O(M \log M)~
• Sắp xếp máy: ~O(N \log N)~
• Mỗi nhiệm vụ được thêm vào multiset một lần, mỗi nhiệm vụ được xóa nhiều nhất một lần
• Mỗi thao tác trên multiset mất ~O(\log M)~

Tổng độ phức tạp:

~O((M + N)\log(M + N))~

Đủ tốt với ~M, N \le 10^5~.

Code C++ tham khảo

Đây là lời giải bạn đã tải lên:

#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)

#define fi   first
#define se   second
#define ALL(v) (v).begin(), (v).end()

#define MAX   220797
const int COEFF_X = 500;
const int COEFF_Y = 2;

int numJob, numMachine;
pair<int, int> jobs[MAX], machines[MAX];
priority_queue<int> jobAt[MAX];

bool Compare(const pair<int, int> &a, const pair<int, int> &b) {
    return a.se != b.se ? a.se < b.se : a.fi < b.fi;
}

void init(void) {
    scanf("%d%d", &numJob, &numMachine);
    FOR(i, 1, numJob) scanf("%d%d", &jobs[i].fi, &jobs[i].se);
    FOR(i, 1, numMachine) scanf("%d%d", &machines[i].fi, &machines[i].se);

    sort(jobs + 1, jobs + numJob + 1, Compare);
    sort(machines + 1, machines + numMachine + 1, Compare);
}

void process(void) {
    long long res = 0;

    multiset<pair<int, int>> choices;
    int j = 1;
    FOR(i, 1, numMachine) {
        while (j <= numJob && jobs[j].se <= machines[i].se) choices.insert(jobs[j++]);
        if (choices.empty()) continue;

        __typeof(choices.begin()) it = choices.upper_bound(machines[i]);
        if (it == choices.begin()) continue;

        it--;
        res += 1LL * COEFF_X * it->fi + 1LL * COEFF_Y * it->se;
        choices.erase(it);
    }

    cout << res << "\n";
}

int main(void) {
    init();
    process();
    return 0;
}