f581. 3. 圓環出口
Tags : APCS 二分搜
Accepted rate : 896人/1069人 ( 84% ) [非即時]
評分方式:
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 (吳宗達) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
37130 fire5386 (becaidorz) f581
題解
595 2023-08-22 18:23
37663 zhoudaniel02 ... (周孝倫) f581
583 2023-09-26 13:48
35436 qerpzzea@gma ... (賽希爾 cecill(陳宥穎)) f581
736 2023-06-03 13:50
33931 willy633526@ ... (ByTech) f581
464 2023-02-14 16:10
33930 willy633526@ ... (ByTech) f581
302 2023-02-14 16:10