🔗 AWC0096A Closing Time of the Reception Window

Problem Statement

題目簡述

有 NN 位訪客依序來到只有一個服務窗口的辦公室。第 ii 位訪客在時間 AiA_i 到達，服務需要 BiB_i 單位時間。窗口從時間 00 開始可用，且必須按照訪客編號順序服務。

每位訪客會在「窗口空閒」且「自己已到達」後立刻開始服務。求最後一位訪客服務結束的時間。

Constraints

約束條件

  • 1≤N≤2×1051 \le N \le 2 \times 10^5
  • 0≤A1≤A2≤⋯≤AN≤1090 \le A_1 \le A_2 \le \cdots \le A_N \le 10^9
  • 1≤Bi≤1091 \le B_i \le 10^9
  • 輸入皆為整數。

思路：依序維護窗口空閒時間

由於窗口一次只能處理一位訪客，且服務順序固定，所以沒有排程選擇，也不用排序；唯一需要維護的是「窗口目前最早什麼時候能接下一位」，即上一位訪客服務結束的時間。

令 E[i]E[i] 為第 ii 位訪客服務結束的時間，則對於下一位訪客，開始服務的時間由兩個條件共同限制：

  • 如果訪客還沒到，就必須等到他的到達時間。
  • 如果窗口還在忙，就必須等到上一位服務結束。

因此開始時間就是這兩個時間的較大值；接著再加上該訪客的服務時間，就能得到新的窗口空閒時間，有以下遞迴式：

E[i]=max⁡(E[i−1],Ai)+BiE[i] = \max(E[i-1], A_i) + B_i

複雜度分析

  • 時間複雜度：O(N)\mathcal{O}(N)
  • 空間複雜度：O(1)\mathcal{O}(1)，只需維護窗口下一次空閒的時間。

Code

1
2
3
4
5
6
7
8
9
10
11
def solve():
    n = int(input())

    ans = 0
    for _ in range(n):
        a, b = map(int, input().split())
        ans = max(ans, a) + b
    print(ans)

if __name__ == "__main__":
    solve()

寫在最後

Cover Image Credit

The cover image was created by @Qurami. All rights belong to the original artist.

It is used here only as a non-commercial cover illustration for this note. I do not claim ownership of the artwork.

If you are the copyright holder and believe this usage is inappropriate, please contact me by email or leave a comment. I will remove the image promptly.