f581: 3. 圓環出口
Tags : APCS 二分搜
Accepted rate : 244人/305人 ( 80% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-01-11 11:27

Content

有 $n$ 個房間排成一個環,編號分別是 $0$ 到 $n-1$。

房間之間有單向的路徑,編號 $i$ 的房間可以走到編號 $(i+1) \mod n$的房間。

每次進入編號 $i$ 的房間可以獲得 $p_i$ 個點數(最一開始待的房間也可以獲得點數)。

現在依序有 $m$ 個任務,第 $i$ 個任務需要蒐集到 $q_i$ 個點數。對於每次的任務,若一開始在編號 $s$ 的房間,且走到編號 $t$ 的房間時候可以蒐集到需要的點數,則完成這次任務後會停在編號 $(t+1)\mod n$ 的房間。

一開始在編號 $0$ 的房間,依據接收到 $m$ 個任務,請求出完成第 $m$ 個任務後會停在哪個編號的房間?

Input

第一行包含兩個正整數 $n, m (1\leq n\leq 200000, 1\leq m \leq 20000)$。

第二行包含 $n$ 個正整數 $p_0, p_1, p_2, \dots, p_{n-1}$,$p$ 的總和不超過 $10^9$。

第三行包含 $m$ 個正整數 $q_0, q_1, q_2, \dots, q_{m-1}$,$q_i$ 不會超過 $p$ 的總和。

 

配分

  • 20分: $1\leq n, m \leq 100$
  • 80分: 同原題目限制。
Output

輸出一個非負整數表示最後停在哪個編號的房間

Sample Input #1
7 3
2 1 5 4 3 5 3
8 9 12
Sample Output #1
4
Sample Input #2
4 3
1 3 5 7
4 2 2
Sample Output #2
0
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (5%): 2.0s , <1K
公開 測資點#1 (5%): 2.0s , <1K
公開 測資點#2 (5%): 2.0s , <1K
公開 測資點#3 (5%): 2.0s , <1K
公開 測資點#4 (5%): 2.0s , <10M
公開 測資點#5 (5%): 2.0s , <10M
公開 測資點#6 (5%): 2.0s , <10M
公開 測資點#7 (5%): 2.0s , <10M
公開 測資點#8 (5%): 2.0s , <10M
公開 測資點#9 (5%): 2.0s , <1M
公開 測資點#10 (5%): 2.0s , <1M
公開 測資點#11 (5%): 2.0s , <1M
公開 測資點#12 (5%): 2.0s , <1M
公開 測資點#13 (5%): 2.0s , <1M
公開 測資點#14 (5%): 2.0s , <1M
公開 測資點#15 (5%): 2.0s , <1M
公開 測資點#16 (5%): 2.0s , <1M
公開 測資點#17 (5%): 2.0s , <1M
公開 測資點#18 (5%): 2.0s , <1M
公開 測資點#19 (5%): 2.0s , <1M
Hint :
Tags:
APCS 二分搜
出處:
2020年7月APCS [管理者:
cthbst (吳宗達)
]


ID User Problem Subject Hit Post Date
26877
showbao (年少有為不自卑)
f581
107 2021-08-30 01:49
26255
timyou (尤耀主)
f581
208 2021-07-28 11:10
24978
bubble60324@... (賢仔)
f581
新手的解題想法
359 2021-04-08 22:55
23998
fire5386 (fffelix)
f581
684 2021-01-08 21:37
23992
089487 (1111)
f581
想法
613 2021-01-08 08:44