如果想將訊號從 A 點傳送到 B 點，需要透過數個基地台依序協助傳遞。
對於每個基地台，已知其 (擺放位置 d) 和 (訊號可向右傳送範圍 r)，
也就是只要被放在 d ~ d+r(包含) 位置範圍內的基地台，皆可收到該基地台的訊號。
給定 N 個由左至右的基地台，
請協助計算如果由最左側也就是編號 1 的基地台發出訊號，向右最遠可傳遞到哪個位置。
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| 第一行有一個正整數 N，代表有 N 個基地台 1 ≤ N ≤ 1000 第二行有 N 個非負整數 di，代表第 i 個基地台所在位置 0 ≤ di ≤ 109 並且保證 d1 = 0 且 d1 ≤ d2 ≤ … ≤ dN 第三行有 N 個非負整數 ri，代表第 i 個基地台訊號可向右範圍 0 ≤ ri ≤ 109 | 由最左側也就是編號 1 的基地台發出訊號， 向右最遠可傳遞到的位置 |
| 5 0 3 5 11 15 3 9 2 2 5 | 13 |
解題思路
將每一個基地台的下一個基地台位置紀錄下來，可以使用陣列的方式來紀錄，這邊命名叫 next。另外，可以使用 map<int, int> 來紀錄每一個基地台可以跑多遠，這邊命名叫 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 掉。
輸出的時候因為可能會有剩餘的步數，所以是輸出 pos + step。
範例程式碼－ZeroJudge N686: 訊號傳遞
#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