【TIOJ 1975】即時工作排程系統(Scheduler)
原題連結: https://tioj.ck.tp.edu.tw/problems/1975 這題很神奇,至於神奇在哪先不馬上劇透(? 首先,當$\color{white}{\space M=0\space}$時,有顯然的$\color{white}{\space O(NlgN)\space}$排序解。 但我們換個角度,把區間的工作視為區間加值,那就有差分後的$\color{white}{\space O(N+C)\space}$解法。 這個解法的關鍵在於只要取被加最多次的點的值就是答案,所以接下來在處理「非即時性工作」時我們也將採取同樣的策略--也就是在加完「即時性工作」後,把每個「非即時性工作」的量分別盡量的、 不重複的 分給 死線前 、 被加的值少 的點,最後再取一次被加最多次的點的值就是答案。 為了方便,我們事先把所有非即時性工作讀進來對死線排序,然後把當前工作$\color{white}{\space i\space}$死線$\color{white}{\space d_i\space}$前的點值全部補進資料結構內,每次拿前$\color{white}{\space w_i\space}$小的值出來每個$\color{white}{\space +1\space}$再丟回去--這是最直觀的寫法了,首先一般我們會想到用pq來維護前k小,但這樣複雜度會是慘慘的$\color{white}{\space O(N+MClgC)\space}$。 於是很自然的也能發現,重複的值太多了,不妨把全部的值全部壓縮在一起綁成pair拿map維護吧! ……結果照樣吃了TLE,因為不能重複分配的關係導致單調性失效。 不過這個壓縮在一起的動作卻是關鍵,可以觀察到,我們是把前$\color{white}{\space w_i\space}$小的值+1,假設被加的值種類分別是$\color{white}{\space v_1,v_2, \cdots ,v_t\space}$,那加值完之後不就只是把前面全部拔掉,變成$\color{white}{\space v_1+1,v_2+1,...,v_{t-1}+1\space}$,並且$\color{white}{\space v_t \space}$被拆成兩份而已嗎!? 這個平移大部份資料位置卻不改變值的動作