APCS Nov 2021 - g597 Q3 [Python]

問題文:

n 台の機械が一列に並び、機械 i はデータ1単位を作るのに t[i] 単位の時間を要します。m 個の仕事があり、仕事 i では位置 [l[i], r[i]] にある各機械が w[i] 単位のデータを作ります。n 台の並び順を変更して、全ての仕事にかかる合計時間を最小化してください。

[name=BlackInk7777] 区間内をループで一つずつ加算すると確実に時間切れになるため、差分配列で高速化します。

---

差分配列の説明

要素数5の配列 dur が全て0だとします：Array = [0,0,0,0,0]。[2,5] の全要素に1を、[3,5] の全要素に2を加えたいとします。

差分配列での処理

1. diff の初期化： diff = [0, 0, 0, 0, 0, 0, 0]。元の配列の末尾より先にも領域を確保します。
2. 最初の区間 [2,4] に加算： 位置2に1を加えて diff = [0, 0, 1, 0, 0, 0, 0]。位置4の次である位置5から1を引き、diff = [0, 0, 1, 0, 0, -1, 0] とします。
3. 次の区間 [3,5] に加算： 位置3に2を加えて diff = [0, 0, 1, 2, 0, -1, 0]。位置5の次である位置6から2を引き、diff = [0, 0, 1, 2, 0, -1, -2] とします。
4. 累積和で dur を復元：
   • i = 1：dur[1] = 0。
   • i = 2：dur[2] = 1（累積で1）。
   • i = 3：dur[3] = 3（1 + 2）。
   • i = 4：dur[4] = 3（3 + 0）。
   • i = 5：dur[5] = 2（3 - 1）。
   • i = 6：dur[6] = 0（2 - 2）。

結果

更新後は dur = [0, 0, 1, 3, 3, 2] です。

---

実装

def main():
    n,m = map(int,input().split())
    dur = [0] * (n + 2)
    diff = [0] * (n + 2)

    for _ in range(m):
        l,r,w = map(int, input().split())
        diff[l] += w
        diff[r+1] -= w

    machine = [int(num) for num in input().split()]

    currect = 0

    for i in range(1 ,len(diff)):
        dur[i] = currect + diff[i]
        currect = dur[i]

    dur.pop(0)
    dur.pop()

    times = 0

    machine.sort(reverse=True)
    dur.sort()

    for i in range(len(dur)):
        times += dur[i] * machine[i]

    print(times)
    
if __name__ == "__main__":
    main()

この問題で使う知識

• 差分配列

• pop の書式：[(配列)].pop(位置)

  例：

  the_list = [0,1,2,3,4]
  the_list.pop(0) // output: [1,2,3,4]
  

この記事は繁体字中国語の原文をAIで翻訳したものです。意味や表現に違いがある可能性があります。正確な内容は繁体字中国語の原文をご確認ください。