Luogu P2862 [USACO06JAN]把牛

YorkWu

September 12, 2019

1284 views

No comments

1265 words

OI 题目

一道双指针+二分答案

- 首先二分边长，主要是check函数怎么写。
- 输入的时候，把每个点都存两次，然后两个数组分别按照x，y坐标排序，然后双指针跑一遍，具体看代码注释。

```cpp
#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;
}
```

Last modification：March 14, 2020