apcs練習網解題紀錄

a132主機排程

相同題型： Q_4_19 五嶽盟主的會議場所

參考測資

範例測資太簡單了導致很多人範測過還是WA，以下測資供參。

Input

1 2
6
1 3 7 2 2 2
1 0 10 1 1 1
2 19 10 4 4 4
1 9 19 8 8 8
2 0 8 16 16 16
1 4 47 32 32 32
0

Output

56 56 56

解法一－先排序再掃描線

$O(s\log s)$

依時間序檢查過每個時間點的資源數增減，可以開兩個陣列用 two pointer 的概念實作（同時有兩個游標在進行追逐戰），也可以偷懶將增與減放進同一陣列，再進行排序。

• 時間複雜度：
  $O(s\times \log s)$
• 空間複雜度：
  $O(s)$

點我看程式-two pointer版

n, D = map(int ,input().split())
for _ in range(n):
    s = int(input())
    L1 = []
    L2 = []
    for _ in range(s):
        td, ts, th, rc, rr, rb = map(int, input().split())
        t = (td-1)*24+ts
        L1.append((t, rc, rr, rb))
        L1.append(((t+24*D, rc, rr, rb)))
        L2.append((t+th, rc, rr, rb))
        L2.append(((t+th+24*D, rc, rr, rb)))
        
    _ = input()
    L1.sort()  
    L2.sort()
    mrc, mrr, mrb = 0, 0, 0
    prc, prr, prb = 0, 0, 0
    RC = []
    j = 0
    for t, rc, rr, rb in L1:
        while L2[j][0] <= t:
            prc -= L2[j][1]
            prr -= L2[j][2]
            prb -= L2[j][3]
            j += 1
        prc += rc; prr += rr; prb += rb
        RC.append(prc)
        mrc = max(mrc, prc)
        mrr = max(mrr, prr)
        mrb = max(mrb, prb)
    print(mrc, mrr, mrb)
    

點我看程式-一個陣列版

n, D = map(int ,input().split())
for _ in range(n):
    s = int(input())
    L = []
    for _ in range(s):
        td, ts, th, rc, rr, rb = map(int, input().split())
        t = (td-1)*24+ts
        L.append((t, rc, rr, rb))
        L.append((t+th, -rc, -rr, -rb))
        L.append((t+D*24, rc, rr, rb))
        L.append((t+th+D*24, -rc, -rr, -rb))

    _ = input()
    L.sort()  #先扣後加
    mrc, mrr, mrb = 0, 0, 0
    prc, prr, prb = 0, 0, 0
    RC = []

    for t, rc, rr, rb in L:
        prc += rc; prr += rr; prb += rb
        RC.append(prc)
        mrc = max(mrc, prc)
        mrr = max(mrr, prr)
        mrb = max(mrb, prb)
    print(mrc, mrr, mrb)

---

解法二－先建立差分序列再掃描線

$O(s+D)$

因為這題的

$D\le 1000$，即使換算小時後再考慮跨週期情形而多開一倍空間

$24D\ast 2\le 48000$。所以可以開一個

$48\ast D$ 格的陣列儲存每一個小時增減的數量，再用前綴和的概念跑一次for迴圈即可得知每個時間的資源數

• 時間複雜度：
  $O(s+D)$
• 空間複雜度：
  $O(s+D)$

註：雖然時間複雜度不考慮常數倍，但這裡的

$D$ 應該用

$24D$ 來計算比較精準

點我看程式

#include <iostream>
using namespace std;

const int MAXD = 2005 * 24;

int main(){
#ifndef debug
    cin.tie(0)->sync_with_stdio(0);
#endif
    int n, D; cin >> n >> D;
    D *= 24;
    while(n--){
        int C[MAXD]={}, R[MAXD]={}, B[MAXD]={};
        int s; cin >> s;
        while(s--){
            int Td, Ts, Th, Rc, Rr, Rb;
            cin >> Td >> Ts >> Th >> Rc >> Rr >> Rb;
            int Tb = (Td-1)*24+Ts;
            C[Tb] += Rc; 
            R[Tb] += Rr;
            B[Tb] += Rb;
            C[(Tb+Th)] -= Rc;
            R[(Tb+Th)] -= Rr;
            B[(Tb+Th)] -= Rb;
        }
        cin >> s; // 0
        int maxc = 0, maxr = 0, maxb = 0;
        int sC = 0, sR = 0, sB = 0;
        for(int i = 0; i < 2*D; i++){
            sC += C[i] + (i>=D)*C[i-D];
            sR += R[i] + (i>=D)*R[i-D];
            sB += B[i] + (i>=D)*B[i-D];
            if(sC > maxc) maxc = sC;
            if(sR > maxr) maxr = sR;
            if(sB > maxb) maxb = sB;
#ifdef debug
            cout << sC << " \n"[i%24==23];
#endif
        }
        cout << maxc << " " << maxr << " " << maxb << '\n';
    }
}