codeforces 617 C. Tourist's Notes (二分)
题目链接 题意：有n天的旅行，但是只剩下了m天的旅行记录，记录格式为d[i],h[d[i]]，表示第i个记录是第d[i]天的，高度为h[d[i]],相邻两天的高度之差的绝对值不超过1.问满足以上条件的最大的h是多少。无解输出impossible. 思路：为了练习二分。 二分高度，然后check是否合法。注意边界，所以可以添加两个点。
/* ***********************************************
Author :111qqz
Created Time :2016年03月30日 星期三 16时53分57秒
File Name :code/cf/problem/538C.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=1E5+7;
7const int M=1E9; //上界并不是h的最大值。。因为还可以继续往上走啊。。
8int n,m;
9int h[N],d[N];
1bool check (int x)
2{
3 // cout<<"x:"<<x<<endl;
1 for ( int i = 1 ; i <= m-1 ; i++)
2 {
3 if (x<h[i]||x<h[i+1]) return true;
4 int cost = abs(x-h[i]) + abs(h[i+1]-x);
5// cout<<"cost:"<<cost<<endl;
6 if (cost<=d[i+1]-d[i]) return true;
7 }
8 return false;
9}
10int bin()
11{
12 int l = 0 ;
13 int r = M ;
14 int mid;
15 while (l<=r)
16 {
17 mid = (l+r)/2;
18 if (check(mid))
19 l = mid + 1;
20 else r = mid -1;
21 }
22 if (r>M) return -1;
23 return r;
24}
25int main()
26{
27 #ifndef ONLINE_JUDGE
28 freopen("code/in.txt","r",stdin);
29 #endif
1 cin>>n>>m;
2 m++;
3 for ( int i = 2 ; i <= m ; i++) cin>>d[i]>>h[i];
1 d[1] = 1;
2 h[1] = h[2] + abs(d[2]-1); //为了处理端点，于是增加两个点。
3 m++;
4 d[m] = n;
5 h[m] = h[m-1] + abs(n-d[m-1]);
1 for ( int i = 1 ; i <= m-1 ; i++)
2 {
3 int tmp = abs(h[i+1]-h[i]);
4 if (d[i+1]-d[i]<tmp)
5 {
6 puts("IMPOSSIBLE");
7 return 0;
8 }
9 }
10 int ans = bin();
11 if (ans==-1)
12 {
13 puts("IMPOSSIBLE");
14 }
15 else
16 cout<<ans<<endl;
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}