hihoCoder #1053 : 居民迁移(贪心，二分搜索，google在线技术笔试模拟)

3  
5 1  
10 80  
20 20  
30 100  
40 30  
50 10  
5 10  
10 80  
20 20  
30 100   
40 30  
50 10  
5 20  
10 80  
50 10  
20 20  
30 100  
40 30 

100  
50  
48
题目链接：https://hihocoder.com/problemset/problem/1053
分析：心塞。自己做了几次都TLE了。不知道怎么把判断是否可行优化到O(n)的时间复杂度。然后就瞄题解了。利用双线性扫描，一线是居民点的坐标point[i].x，二线是每个居民点所能迁移的范围width[]。扫描过程中使用_point和_n记录上一次width[]点的位置和值
就是写不来！只能模拟一下别人写的了！
下面给出AC代码：

 1 #include<map>
 2 #include<queue>
 3 #include<stack>
 4 #include<cmath>
 5 #include<cstdio>
 6 #include<string>
 7 #include<cstring>
 8 #include<iostream>
 9 #include<algorithm>
10 using namespace std;
11 typedef long long ll;
12 
13 const int maxn = 100000 + 5;
14 
15 int T;
16 int maxy;
17 int p,k,R;
18 struct Node{int x,y;}point[maxn];
19 struct node{int l,r,n;}width[maxn];
20 bool cmp(Node d,Node e){return d.x<e.x;}
21 
22 void input(){
23     scanf("%d%d",&p,&R);
24     for(int i=0;i<p;i++){
25         scanf("%d%d",&point[i].x,&point[i].y);
26     }
27 }
28 
29 void new_arrow(){
30     sort(point,point+p,cmp);
31     maxy=0;k=p-1;
32     for(int i=0;i<=k;i++){
33         if(point[i].y>maxy) maxy=point[i].y;
34         width[i].l=point[i].x-R;
35         width[i].r=point[i].x+R;
36         width[i].n=point[i].y;
37     }
38 }
39 
40 bool check(int middle){
41     int _point=0,_n=point[0].y;
42     for(int i=0;i<=k;i++){
43         int pose=point[i].x;
44         int num=middle;
45         if(width[_point].r<pose)
46             return false;
47         int j;
48         for(j=_point;j<=k+1;j++){
49             if(j==k+1) return true;
50             if(width[j].l>pose){
51                 _point=j;
52                 _n=width[j].n;
53                 break;
54             }
55             int cnt;
56             if(j==_point) cnt=_n;
57             else cnt=width[j].n;
58             num-=cnt;
59             if(num<0){
60                 _point=j;
61                 _n=0-num;
62                 break;
63             }
64         }
65     }return false;
66 }
67 
68 int Binary_search(){
69     int l=0,r=maxy,mid=0;
70     while(r-l>1){
71         mid=(l+r)>>1;
72         if(check(mid)) r=mid;
73         else l=mid;
74     }return r;
75 }
76 
77 void solve(){
78     new_arrow();
79     printf("%d\n",Binary_search());
80 }
81 
82 int main(){
83     scanf("%d",&T);
84     while(T--){
85         input();
86         solve();
87     }return 0;
88 }