Luogu P2862 [USACO06JAN]把牛

一道双指针+二分答案

  • 首先二分边长,主要是check函数怎么写。
  • 输入的时候,把每个点都存两次,然后两个数组分别按照x,y坐标排序,然后双指针跑一遍,具体看代码注释。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
using namespace std;

struct node{
int x, y;
};

bool cmpx(const node &a, const node &b){
return a.x == b.x ? a.y < b.y : a.x < b.x;
}

bool cmpy(const node &a, const node &b){
return a.y == b.y ? a.x < b.x : a.y < b.y;
}

struct Solution{
int n, c;
vector<node> xc, yc;

int getSum(int l, int len){
int res = 0;
int r = l + len - 1;
vector<int> ls;
ls.push_back(0);
for(int i = 1; i <= n; i++){
if(yc[i].x >= l && yc[i].x <= r){
ls.push_back(yc[i].y);
//把横坐标l到r的所有点按照纵坐标的顺序保存一下,方便一会上指针。
}
}
int pl = 1, pr = 1;
while(pr < ls.size() && ls[pr] - ls[pl] + 1 <= len) pr++;
if(pr >= ls.size() || ls[pr] - ls[pl] + 1 > len) pr--;
//上面while和if初始化一下pr,使pl到pr里面的纵坐标满足条件。
while(pr < ls.size() && pl <= pr){
res = max(res, pr - pl + 1);
//保存一下在整个过程在满足mid限制条件的情况下,最多在栅栏里能有多少点。
pr++;
while(ls[pr] - ls[pl] + 1 > len) pl++;
//往右继续扫。
}
return res;
}

bool check(int mid){
for(int i = 1; i <= n; i++){
//这里枚举一下左端点。
if(getSum(xc[i].x, mid) >= c){
//如果有一种情况使其达到要求,返回true。
return true;
}
}
return false;
}

void Solve(){
scanf("%d%d", &c, &n);
xc.resize(n + 1);
yc.resize(n + 1);
for(int i = 1; i <= n; i++){
scanf("%d%d", &xc[i].x, &xc[i].y);
yc[i].x = xc[i].x, yc[i].y = xc[i].y;
}
sort(xc.begin() + 1, xc.end(), cmpx);
sort(yc.begin() + 1, yc.end(), cmpy);
int l = 0, r = 10010;
while(l < r){
int mid = (l + r) >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
printf("%d\n", l);
}
};

int main(){
Solution().Solve();
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×