codeforces 617 C. Tourist's Notes (二分)
题目链接 题意：有n天的旅行，但是只剩下了m天的旅行记录，记录格式为d[i],h[d[i]]，表示第i个记录是第d[i]天的，高度为h[d[i]],相邻两天的高度之差的绝对值不超过1.问满足以上条件的最大的h是多少。无解输出impossible. 思路：为了练习二分。 二分高度，然后check是否合法。注意边界，所以可以添加两个点。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年03月30日 星期三 16时53分57秒
4File Name :code/cf/problem/538C.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E5+7;
34const int M=1E9; //上界并不是h的最大值。。因为还可以继续往上走啊。。
35int n,m;
36int h[N],d[N];
37
38
39
40bool check (int x)
41{
42 // cout<<"x:"<<x<<endl;
43
44 for ( int i = 1 ; i <= m-1 ; i++)
45 {
46 if (x<h[i]||x<h[i+1]) return true;
47 int cost = abs(x-h[i]) + abs(h[i+1]-x);
48// cout<<"cost:"<<cost<<endl;
49 if (cost<=d[i+1]-d[i]) return true;
50 }
51 return false;
52}
53int bin()
54{
55 int l = 0 ;
56 int r = M ;
57 int mid;
58 while (l<=r)
59 {
60 mid = (l+r)/2;
61 if (check(mid))
62 l = mid + 1;
63 else r = mid -1;
64 }
65 if (r>M) return -1;
66 return r;
67}
68int main()
69{
70 #ifndef ONLINE_JUDGE
71 freopen("code/in.txt","r",stdin);
72 #endif
73
74 cin>>n>>m;
75 m++;
76 for ( int i = 2 ; i <= m ; i++) cin>>d[i]>>h[i];
77
78 d[1] = 1;
79 h[1] = h[2] + abs(d[2]-1); //为了处理端点，于是增加两个点。
80 m++;
81 d[m] = n;
82 h[m] = h[m-1] + abs(n-d[m-1]);
83
84
85 for ( int i = 1 ; i <= m-1 ; i++)
86 {
87 int tmp = abs(h[i+1]-h[i]);
88 if (d[i+1]-d[i]<tmp)
89 {
90 puts("IMPOSSIBLE");
91 return 0;
92 }
93 }
94 int ans = bin();
95 if (ans==-1)
96 {
97 puts("IMPOSSIBLE");
98 }
99 else
100 cout<<ans<<endl;
101
102 #ifndef ONLINE_JUDGE
103 fclose(stdin);
104 #endif
105 return 0;
106}