第一题：爬山
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
题目描述：
小B曾经酷爱网络游戏，整日通宵达旦的玩游戏，导致身体素质急剧下降，因此下决心痛改前非，远离一切电子产品，并通过远足爬山的方式改变生活方式并提高身体素质。由于担心对身体造成太大的负荷，他总是选择最平坦的路径，并记录每天的行程情况及达到的最高海拔，使得连续两天之间的海拔之差最多为一个单位。不幸的是，在行程结束时，他不小心掉进河里，造成部分记录信息遗失。他想知道自己行程中可能达到的最高海拔，你是否能够帮忙？
输入
输入有若干组，每组的第一行为空格分隔的两个整数n和m，1<=n<=10^8, 1<=m<=10^5，分别表示行程天数以及未遗失的记录数。随后紧跟m行，每行为空格分隔的两个整数d和h，1<=d<=n, 0<=h<=10^8，表示行程的第几天及当天达到的最高海拔。
输出
对每组输入，如果记录是可能的，则在单独的行中输出可能达到的最高海拔，否则输出字符串“IMPOSSIBLE”（不含引号）。
样例输入
8 2
2 0
7 0
8 3
2 0
7 0
8 3
样例输出
2
IMPOSSIBLE
这个题目看起来比较绕，先拿测试用例说明情况吧，第2天是0，第7天也是0，以第二天为例，说明这两天其相当于一步没动，相对之前的高度是0米，而时间是2天。那么其相对最高高度可能是(相对天数 - 相对高度) / 2 = (2 - 0)/2 = 1,由于一开始的高度是0，所以最高高度=前一次记录的高度+相对最高高度=0 + 1 = 1,所以第二天最高是1。得到下面计算相对最高高度
hx = (h - hpre) + ((d - dpre) - (h - hpre)) / 2,
temphighest = hx + hpre;
highest = max(temphighest,highest)
#include <iostream>
#include <string>
using namespace std;
int main() {
int m,n;
int d,h;
while (cin >>n>>m) {
int highest = 0;//最高结果
int tempest = 0;//暂时的最高点
int dpre = 0;//前一条记录的天数
int hpre = 0;//前一条记录的高度
bool flag = true;//判断其是否合法
while (m--){
flag = true;
cin>>d>>h;
if ((h - hpre) > (d - dpre)) {
cout<<"IMPOSSIBLE"<<endl;
flag = false;
break;
}
int xhigh = (h - hpre)+ ((d - dpre) - (h - hpre)) / 2;//得到的是相对于前一条记录的高度
tempest = xhigh + hpre; //得到两条记录之前能达到的最大高度
if (tempest > highest) {
highest = tempest;
}
hpre = h;
dpre = d;
}
//判断一下最后的情况
tempest = (n - dpre) + hpre;//算一下最后的情况
if (tempest > highest) {
highest = tempest;
}
if (flag) {
cout<<highest<<endl;
}
}
return 0;
}