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
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line contains a positive integer N, representing the number of base stations.
1 ≤ N ≤ 1000 The second line contains N non-negative integers, di, representing the positions of the ith base station. 0 ≤ di ≤ 10^9 It's guaranteed that d1 = 0 and d1 ≤ d2 ≤ … ≤ dN. The third line contains N non-negative integers, ri, representing the signal range of the ith base station. 0 ≤ ri ≤ 10^9 | The farthest position to which a signal can be transmitted if it is emitted from the leftmost base station, numbered 1. |
| 5 0 3 5 11 15 3 9 2 2 5 | 13 |
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.
Run a for loop from 0 to N-2, and declare two variables pos = 0 and step = MAP[0], representing the current position and the remaining steps respectively. If pos + step >= next[i], meaning that the current position plus the remaining steps can reach the next base station, update pos to next[i] and set step -= next[i] - pos. Then compare whether the remaining steps step is greater or MAP[next[i]], which is the steps provided by the new base station, is greater, and set the greater value as the new step. If it's not possible to reach the next base station, break the for loop.
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