---
title: apcs練習網解題紀錄
---

# apcs練習網解題紀錄

## [a132主機排程](https://apcsclass.csie.ntnu.edu.tw/ShowProblem?problemid=a132)

> 相同題型： [Q_4_19 五嶽盟主的會議場所](https://jmj.cmgsh.tp.edu.tw/ShowProblem?problemid=d061)

### 參考測資
範例測資太簡單了導致很多人範測過還是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)$

::: spoiler 點我看程式-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)
    

:::

:::spoiler 點我看程式-一個陣列版

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*2 \le 48000$。所以可以開一個 $48*D$ 格的陣列儲存每一個小時增減的數量，再用前綴和的概念跑一次`for`迴圈即可得知每個時間的資源數

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

*註：雖然時間複雜度不考慮常數倍，但這裡的 $D$ 應該用 $24D$ 來計算比較精準*

:::spoiler 點我看程式

#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';
    }
}

:::