Codeforces Round #200 (Div. 2) E. Read Time(二分)

这题，关键不是二分，而是如果在t的时间内，将n个头，刷完这m个磁盘。

看了一下题解，完全不知怎么弄。用一个指针从pre，枚举m，讨论一下。只需考虑，每一个磁盘是从右边的头，刷过来的（左边来的之前刷了）。

思维是硬伤。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <vector>
 5 #include <cmath>
 6 #include <algorithm>
 7 using namespace std;
 8 #define LL __int64
 9 LL p[100001],h[100001];
10 int n,m;
11 int judge(LL x)
12 {
13     int pre = 0;
14     LL temp;
15     int i;
16     for(i = 0;i < n;i ++)
17     {
18         if(abs(p[pre]-h[i]) > x) continue;
19         if(p[pre] < h[i])
20         temp = h[i] + max((x-(h[i]-p[pre]))/2,x-2*(h[i]-p[pre]));
21         else
22         temp = h[i] + x;
23         while(p[pre] <= temp&&pre < m)pre ++;
24     }
25     if(pre == m)
26     return 1;
27     else
28     return 0;
29 }
30 LL bin()
31 {
32     LL str,end,mid;
33     str = 0;
34     end = 100000000000000ll;
35     while(str < end)
36     {
37         mid = (str + end)/2;
38         if(judge(mid))
39         end = mid;
40         else
41         str = mid + 1;
42     }
43     return str;
44 }
45 int main()
46 {
47     int i;
48     scanf("%d%d",&n,&m);
49     for(i = 0;i < n;i ++)
50     {
51         scanf("%I64d",&h[i]);
52     }
53     for(i = 0;i < m;i ++)
54     {
55         scanf("%I64d",&p[i]);
56     }
57     printf("%I64d
",bin());
58     return 0;
59 }