Note
For the first sample, an example of a correct height sequence with a maximum of 2:(0,0,1,2,1,1,0,1).
In the second sample the inequality betweenh7andh8does not hold, thus the information is inconsistent.
题意：一个旅行者在外旅行n天，第i天所在地方的海拔为hi，，相邻两天的海拔之差不超过1。给出部分天数的海拔，问这个人在这n天中，所到地方的最高海拔是多少？如果根据给出的数据不符合题意描述，即出现相邻两天的海拔之差超过1，输出“IMPOSSIBLE”。
分析：对于给出第一条数据（a，b），假设从第一天到第a天一直减1，则第一天的海拔为 b + (a – 1)；从第pre_a天海拔为pre_b，到第a天海拔为b，假设中间的最高海拔为x，则可列出不等式（x – pre_b) + (x – b) <= a – pre_a，整理得x = （pre_b + b + a – pre_a）/ 2；从最后一条数据（a，b）到第n天，假设一直加1，则第n天的海拔为b+(n-a)。每次求出一个值，求出他们的最大值即可。
#include <iostream>#include <string>#include <vector>#include <cstdio>#include <cstdlib>#include <algorithm>using namespace std;int main() {int n, m, a, b;while(cin >> n >> m) {cin >> a >> b;int pre_a = a, pre_b = b;int ans = b + a – 1; // 假设从第一天到第a天一直减1bool flag = true;for(int i = 1; i < m; i++) {cin >> a >> b;if(abs(b – pre_b) > a – pre_a) flag = false; //相邻两天的海拔之差大于1int tmp = (pre_b + b + a – pre_a) / 2;ans = max(ans, tmp);pre_a = a;pre_b = b;} //假设从第pre_a天到第a天的最大高度为h，则（h-pre_b)+(h-b)<=(a-pre_a),整理的h=(pre_b+b+a-pre_a)/2int tmp = pre_b + (n – pre_a); //从第pre_b天到第n天一直加1ans = max(ans, tmp);if(flag) cout << ans << endl;else cout << "IMPOSSIBLE" << endl;}return 0;}
对的，坚持;错的，放弃!
