TIOJ 1975：即時工作排程系統（Scheduler）

TIOJ 1975：即時工作排程系統（Scheduler）

題目大意：有 $n$ 個即時工作和 $m$ 個非即時工作，即時工作以 $(l,r)$ 表示，代表這個工作在 $[l, r]$ 要被處理，非即時工作以 $(w, d)$ 表示，代表要在時間點 $d$ 以前處理了長度為 $w$ 的時間，且同時最多只能有一臺機器處理此工作。每臺機器同時最多只能處理一個工作，問你最少需要幾臺機器才能把全部工作做好。

解法：首先即時的工作可以用差分維護每個時間點有幾臺機器在運作，把非即時的工作按照 $d$ 排好，用一個 $\text{treap}$ 記錄目前的時間點裡有 $i$ 臺機器在運作的有幾個，如果要工作 $w$ 的時間，就相當於把最小的 $w$ 個 $i$ 變成 $i+1$，這個 $\text{treap}$ 除了要可以以大小 $\text{split}$ 之外，也要支援以總和 $\text{split}$ 的功能。

$\text{Code：}$

#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout<<"["<<#HEHE<<"] = ",dout(HEHE)
void dout(){cerr<<endl;}
template<typename T,typename...U>
void dout(T t,U...u){cerr<<t<<(sizeof...(u)?", ":""),dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a,I=b;x<=I;x++)
#define pb emplace_back
#define F first
#define S second

#define rnd(l,r) uniform_int_distribution<int>(l,r)(seed)
mt19937 seed (time (NULL));

#define siz(t) (t?t->siz:0)
#define cnt(t) (t?t->cnt:0)
#define sum(t) (t?t->sum:0)

struct T {
    int prior = rnd (0, 2e9);
    int siz = 1, cnt = 0, sum = 0;
    T *ls = NULL, *rs = NULL;
    void Pull() {
        siz = 1 + siz (ls) + siz (rs);
        sum = cnt + sum (ls) + sum (rs);
    }
};

T *Merge (T *a, T *b) {
    if (!a || !b) return a ? a : b;
    if (a->prior <= b->prior) {
        a->rs = Merge (a->rs, b);
        a->Pull();
        return a;
    } else {
        b->ls = Merge (a, b->ls);
        b->Pull();
        return b;
    }
}

void Split (T *t, T *&a, T *&b, int k) {
    if (!t) {
        a = b = NULL;
        return;
    }
    if (k <= siz (t->ls)) {
        b = t;
        Split (t->ls, a, b->ls, k);
        b->Pull();
    } else {
        a = t;
        Split (t->rs, a->rs, b, k - siz (t->ls) - 1);
        a->Pull();
    }
}

void Split2 (T *t, T *&a, T *&b, int k) {
    if (!t) {
        a = b = NULL;
        return;
    }
    if (k <= sum (t->ls)) {
        b = t;
        Split2 (t->ls, a, b->ls, k);
        b->Pull();
    } else if (k <= sum (t->ls) + t->cnt) {
        a = t->ls;
        b = t, b->ls = NULL;
        b->Pull();
    } else {
        a = t;
        Split2 (t->rs, a->rs, b, k - sum (t->ls) - t->cnt);
        a->Pull();
    }
}

const int SIZE = 1e5 + 5;
const int MAX = 1e6 + 5;

int n, mx;
int cnt[MAX];
pair<int, int> a[SIZE];

T *t = new T();

void Add (int p, int x) {
    if (!x) return;
    while (siz (t) - 1 < p) t = Merge (t, new T());
    T *t1, *t2;
    Split (t, t1, t, p);
    Split (t, t, t2, 1);
    t->cnt += x;
    t->sum += x;
    t = Merge (t1, Merge (t, t2));
}

void Move (int x) {
    if (!x) return;
    T *t1, *t2;
    Split2 (t, t1, t, x);
    Split (t, t, t2, 1);
    int p = siz (t1), c = cnt (t);
    x -= sum (t1);
    t = Merge (new T(), Merge (t1, t2));
    Add (p, c - x);
    Add (p + 1, x);
}

void solve() {
    cin >> n;
    FOR (i, 1, n) {
        int l, r;
        cin >> l >> r;
        cnt[l]++;
        cnt[r + 1]--;
        mx = max (mx, r);
    }
    cin >> n;
    FOR (i, 1, n) {
        cin >> a[i].S >> a[i].F;
        mx = max (mx, a[i].F);
    }
    a[++n] = {mx + 1, 0};
    sort (a + 1, a + n + 1);
    int pos = 1, sum = 0;
    FOR (i, 1, n) {
        auto [d, w] = a[i];
        while (pos <= d) {
            sum += cnt[pos];
            Add (sum, 1);
            pos++;
        }
        Move (w);
    }
    cout << siz (t) - 1 << '\n';
}

int main() {
    Waimai;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！