APCS Nov 2021 - g597 Q3 [Python]

Problem statement:

There are n machines in a row. Machine i takes t[i] units of time to produce one unit of data. There are m jobs; job i requires each machine at positions [l[i], r[i]] to produce w[i] units of data. You may rearrange the n machines to minimize the total time needed to complete all m jobs.

[name=BlackInk7777] Adding each range with a loop would definitely time out, so we use a difference array to speed this up.

---

How difference arrays work

Suppose dur is an array of size 5, initially all zeros: Array = [0,0,0,0,0]. We want to add 1 to every element in [2,5] and add 2 to every element in [3,5].

Applying a difference array

1. Initialize diff: diff = [0, 0, 0, 0, 0, 0, 0]. The difference array includes extra space beyond the original array.
2. Add to the first interval [2,4]: Add 1 at position 2: diff = [0, 0, 1, 0, 0, 0, 0]. Subtract 1 at position 5, immediately after position 4: diff = [0, 0, 1, 0, 0, -1, 0].
3. Add to the second interval [3,5]: Add 2 at position 3: diff = [0, 0, 1, 2, 0, -1, 0]. Subtract 2 at position 6, immediately after position 5: diff = [0, 0, 1, 2, 0, -1, -2].
4. Recover dur using cumulative sums:
   • i = 1: dur[1] = 0.
   • i = 2: dur[2] = 1 (cumulative sum 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).

Result

The updated array is dur = [0, 0, 1, 3, 3, 2].

---

Implementation

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()

Key concepts

• Difference arrays

• pop syntax: [(array)].pop(index)

  Example:

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

This article was translated from Traditional Chinese by AI. Meaning or wording may differ; please refer to the Traditional Chinese original as the authoritative version.