h074. Chinese Restaurant (Harder Version) - 高中生程式解題系統

內容

有 $n$ 個人，編號 $0$ ~ $n - 1$ ，圍坐在一個圓桌旁，並且相鄰的兩個人的間距都是相等的。

一開始，第 $i$ 個人的面前有餐點 $p_{i} (0 \leq p_{i} \leq n - 1)$ 。
你可以在開始用餐前任意地旋轉圓桌，假如你旋轉了一個餐點的距離，本來在第 $i$ 個人的面前的餐點會變成在第 $(i + 1) \mod n$ 個人面前。

每個人都有一個可以夾菜的距離，第 $i$ 個人可以夾菜的距離是 $c_{i}$ ，表是他可以吃到順時鐘或逆時鐘方向距離 $c_{i}$ 道餐點以內的所有餐點。
例子：有 $10$ 個人，第 $5$ 個人的夾菜距離是 $2$ ，表示他可以吃到位置 $[5 - 2, 5 + 2]$ = $[3, 7]$ 範圍的菜。

已知第 $i$ 個人最喜歡的餐點是編號 $i$ 的餐點，請在開始用餐前找到最好的圓桌旋轉方式（開始用餐用就不能再旋轉圓桌），讓盡可能多人能夾到自己喜歡吃的餐點。
輸出最多有幾個人可以夾到自己喜歡吃的餐點。

輸入說明

輸入的第一行有一個非負整數 $n (1 \leq n \leq 200000)$ ，表示人數。

接下來有 $n$ 行，第 $i + 1$ 行有兩個數字 $p_{i} (0 \leq p_{i} < n)$ 和 $c_{i} \leq (n - 1) / 2$ 分別表示編號 $i$ 的人面前一開始的餐點編號以及第 $i$ 個人的夾菜距離。

輸出說明

輸出一個整數表示在最好的旋轉方式下最多有多少人可以夾到自己喜歡的餐點。

範例輸入 #1

範例輸出 #1

範例輸入 #2

範例輸出 #2

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (20%): 2.0s , <10M
公開測資點#1 (20%): 2.0s , <10M
公開測資點#2 (20%): 2.0s , <10M
公開測資點#3 (20%): 2.0s , <10M
公開測資點#4 (20%): 2.0s , <10M

提示：

標籤:

前綴和差分掃描線線段線段樹

出處:

AtCoder ABC_268C [管理者： edison1998402@gmail.com

cthbst (吳宗達) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」