703 . 補給兵問題
TopCoder
Tags
Description
南宋年間，蒙古大軍自北方入侵中原，烽火四起，百姓生靈塗炭、苦不堪言。南宋趙氏朝廷退至臨安，坐守南方膏腴之地。其中，襄陽城堪稱通往南方的咽喉。現在，蒙古兵臨城下，干戈四起，守城將領已經做好準備了，而你則是負責運送砲彈的小兵。
已知襄陽城的城牆上有 $N$ 個哨站，編號為 $0$ 至 $N - 1$，呈環狀排列，且對於所有的 $0 \le i < N$，編號 $i$ 的哨站有一條單行道通往編號 $(i + 1) \mod N$ 的哨站。每一個哨站有各自對於砲彈的需求量，一個正整數 $p_i$ 代表第 $i$ 個哨站需要 $p_i$ 石的砲彈。而一旦你經過了一個哨站，你就會恰將 $p_i$ 石的砲彈給那個哨站。一開始你在編號為 $0$ 的哨站，而你將收到 $M$ 個型如「請送出至少 $q_i$ 個砲彈」的任務。也就是說，你會從現在這個哨站開始送砲彈，然後走到下一個哨站繼續送，直到送出的砲彈數量達到 $q_i$ 個為止。如果你從編號為 $s$ 的哨站開始，送到編號 $t$ 的哨站剛好送出足夠的砲彈的話，則你會停在編號為 $(t + 1) \mod N$ 的哨站，才算任務完成（$0 \le s, t < N$）。
給定以上的資訊，請問你最後會停在哪個哨站？
Input Format
輸入將有 $3$ 行。第一行包含兩個正整數 $N, M(1 \leq N \le 200000, 1 \le M \le 20000)$。第二行將包含 $N$ 個正整數，第 $i$ 個數字代表 $p_{i - 1}(\sum_{i = 0}^ {N - 1} p_i \leq 10^ {9})$。最後一行將有 $M$ 個正整數，其中第 $j$ 個代表 $q_j(q_j \leq \sum_{i = 0}^ {N - 1} p_i)$。
此外，對於佔分 $20\%$ 的測試資料，還額外滿足 $1 \le N, M \le 100$。
Output Format
請輸出一個數字 $k$，代表最後你會停在哪一個哨站。
Sample Input 1
1 1 1 1 1
1 2 3
Sample Output 1
Sample Input 2
1 2 4 8 16 32
31 32 15
Sample Output 2
Sample Input 3
7 1 2 2 7 1 2 2
7 1 2 3 9 8 7 2
Sample Output 3
Hints
Problem Source
APCS 202007 第 3 題
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測資 | 0 |
| 2 | 0~16 | $1 \le n, m \le 100$ | 20 |
| 3 | 0~35 | 無額外限制 | 80 |