codeforces 479D. Long Jumps
http://codeforces.com/problemset/problem/479/D
题意是说有一把尺子，本身有一些刻度，然后需要测量x和y，问最少需要添加多少个刻度，如果需要，这些刻度分别添加在什么位置。
一开始没有看清题目，以为答案最多为4，但是发现，a[1]=0 a[n]=l这两个是确定的，所以答案最多为2，
而不会出现中间有两个刻度，无论是往前刻还是往后都会越界的情况。
先去看看已知的刻度里有没有直接满足的。
除此之外，如果在已知的刻度下无法测量x也无法测量y，我们还可以找找是否能有公用点使得只刻一个刻度就可以满足题意。公用点分两种情况，一种是在两个刻度之间，另一种是在两个刻度的同侧。
前一种没什么坑，后一种要判断是否越界！！！
如果在已知的刻度下能测量x或者能测量出y但不能同时测量的话，就没有必要找公用点。
还有就是查找的话如果线性找复杂度是O(n2)，会TLE在第27个点。
我们用二分...
话说STL里竟然连二分查找也有。。。。简直orz。。。。真是省时省力。
代码：
1
2
3 /* ***********************************************
4 Author :111qqz
5 Created Time :2016年02月22日 星期一 23时42分46秒
6 File Name :code/cf/problem/479D.cpp
7 ************************************************ */
8
9 #include <iostream>
10 #include <algorithm>
11 #include <cstring>
12 #include <cstdio>
13 #include <cmath>
14
15 using namespace std;
16
17 int n,l,x,y;
18 const int N=1E5+7;
19 int a[N];
20 int ans,p,q;
21 bool flag1,flag2,flag3,flag4;
22
23 int main()
24 {
25 scanf("%d %d %d %d",&n,&l,&x,&y);
26 flag1 = false;
27 flag2 = false;
28 flag3 = false;
29 flag4 = false;
30
31 for ( int i = 1 ; i <= n ; i++ )
32 scanf("%d",&a[i]);
33 ans = 2;
34 p = -1;
35 q = 0;
36 for ( int i = 1 ; i <= n ; i++ )
37 {
38 if(binary_search(a,a+n+1,a[i]+x))
39 {
40 flag1 = true;
41
42 }
43 if (binary_search(a,a+n+1,a[i]+y))
44 {
45 flag2 = true;
46 }
47 if (binary_search(a,a+n+1,a[i]+x+y))
48 {
49 flag3 = true;
50 p = a[i];
51 }
52 if (binary_search(a,a+n+1,a[i]+y-x)&&((a[i]+y<=l)||(a[i]-x>=0)))
53 {
54 flag4 = true;
55 p = a[i];
56 }
57 }
58
59 if ( flag1) {ans--;q = 1 ;}
60 if ( flag2 ){ ans--;q = 2 ;}
61 if ( ans==2&&(flag3||flag4))
62 {
63 ans--;
64 }
65 cout<<ans<<endl;
66 if ( ans==2 )
67 {
68 cout<<a[1]+x<<" "<<a[1]+y<<endl;
69 }
70 if ( ans==1 )
71 {
72 if ( p==-1 )
73 {
74 if ( q==1 )
75 cout<<a[1]+y<<endl;
76 else cout<<a[1]+x<<endl;
77 }
78 else
79 {
80 if ( p+y<=l )
81 cout<<p+y<<endl;
82 else cout<<p-x<<endl;
83 }
84 }
85 return 0;
86 }
87
88