ZeroJudge N686: Signaling

If you want to transmit a signal from point A to point B, you need to pass through several base stations in sequence to assist in transmission.

For each base station, its location (placement position d) and the range (signal transmission range r) are known. This means that any base station placed within the range from d to d+r (inclusive) can receive signals from that base station.

Given N base stations from left to right, please help calculate the farthest position to which a signal can be transmitted if it is emitted from the leftmost station, which is numbered 1.

Sample Inputs/Outputs

Thought Process

Record the position of the next base station for each base station. This can be done using an array, which we'll name next. Additionally, use map to record how far each base station can reach, and we'll name this MAP.

跑一個 For迴圈 從 0 到 N-2，並且宣告兩個變數 pos = 0、step = MAP[0]，分別代表目前的位置和還有幾步可以走。如果 pos + step >= next[i]，也就是當目前位置＋剩餘步數可以抵達下一個基地台時，將 pos 更新成 next[i]，並且將 step -= next[i] – pos。之後要來比對是目前剩餘的步數 step 比較多，還是 MAP[next[i]] 也就是新基地台提供的步數比較多，將多者設定為新的 step。如果無法抵達下一個基地台，則將 For迴圈 Break 掉。

When output, since there might be remaining steps, output pos + step.

Sample Code－ZeroJudge N686: Signaling

#include <iostream>
#include <map>
#include <vector>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    vector<int>num, next;
    map<int, int>MAP;
    for (int i = 0; i<N; i++) {
        int tmp;
        cin >> tmp;
        num.push_back(tmp);
        if (i != 0) next.push_back(tmp);
    }
    for (int i = 0; i<N; i++) {
        int tmp;
        cin >> tmp;
        MAP[num[i]] = tmp;
    }
    int pos = 0, step = MAP[0];
    for (int i = 0; i<N-1; i++) {
        if (pos + step >= next[i]) {
            step -= next[i] - pos;
            pos = next[i];
            step = max(step, MAP[next[i]]);
        }
        else break;
    }
    cout << pos + step << "\n";
}

//ZeroJudge N686
//Dr. SeanXD