ZeroJudge F581: 圓環出口

有 n 個房間排成一個環，編號分別是 0 到 n−1。

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

每次進入編號 i 的房間可以獲得 pi 個點數（最一開始待的房間也可以獲得點數）。

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

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

範例測資

範例輸入範例輸出
第一行包含兩個正整數 N 和 M (1 <= N <= 200000、1 <= M <= 20000)。
第二行包含 N 個正整數 Pi，P 的總和不超過 109。
第三行包含 M 個正整數 Qi，Qi 不會超過 P 的總和。		輸出一個非負整數表示最後停在哪個編號的房間。
7 3
2 1 5 4 3 5 3
8 9 12		4
4 3
1 3 5 7
4 2 2		0
ZeroJudge F581 範例測資

解題思路

使用二分搜尋，只是目標改成 Qi + 目前位置的前綴和，並且要將結果 % N。如果目標大於最大的前綴和 (最後一個數字)，則將目標 -= 最大前綴和。最後輸出最終位置即可。

範例程式碼－ZeroJudge F581: 圓環出口

#include <iostream>
using namespace std;

int N, M, num[200000] = {}, prefix[200000] = {};

int binary(const int L, const int R, const int target) {
    if (L >= R) return R;
    const int middle = (L+R)/2;
    if (target > prefix[middle]) {
        return binary(middle+1, R, target);
    }
    return binary(L, middle, target);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    int sum = 0;
    prefix[0] = 0;
    for (int i = 0; i<N; i++) {
        cin >> num[i];
        sum += num[i];
        prefix[i+1] = sum;
    }
    int position = 0;
    for (int i = 0; i<M; i++) {
        int Q;
        cin >> Q;
        int target = Q+prefix[position];
        if (target > prefix[N]) target -= prefix[N];
        position = binary(0, N, target) % N;
    }
    cout << position << "\n";
}

//ZeroJudge F581
//Dr. SeanXD
標籤

相關文章

發佈留言