POJ - 3179 Corral the Cows（二分，离散化，前缀和）

POJ - 3179 Corral the Cows

#include<iostream>
#include<vector>
#include<algorithm>
#define x first
#define y second
using namespace std;typedef pair<int,int>PII;
const int N = 1010;int n,c;
int sum[N][N];	   //前缀和 
vector<PII>points; //点的坐标
vector<int>numbers;//离散化结果int get_id(int n)
{
    int l=0,r=numbers.size()-1;while(l<r){
    int mid=l+r>>1;if(numbers[mid]>=n) r=mid;else l=mid+1;} return r;
} bool check(int len)
{
    for(int x1=1,x2=1;x2<numbers.size();x2++){
    while(numbers[x2]-numbers[x1]+1>len) x1++;for(int y1=1,y2=1;y2<numbers.size();y2++){
    while(numbers[y2]-numbers[y1]+1>len) y1++;if(sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]>=c) return true;//因为包括边界，所以左上角坐标需要-1}}return false;
} int main()
{
    cin>>c>>n;numbers.push_back(0);for(int i=0;i<n;i++){
    int x,y;cin>>x>>y;numbers.push_back(x);numbers.push_back(y);points.push_back({
    x,y});}sort(numbers.begin(),numbers.end());numbers.erase(unique(numbers.begin(),numbers.end()),numbers.end());//因为相同的数字只需要一个离散化的结果for(int i=0;i<n;i++){
    int x=get_id(points[i].x),y=get_id(points[i].y);sum[x][y]++;}for(int i=1;i<numbers.size();i++)for(int j=1;j<numbers.size();j++)sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];int l=1,r=10010;while(l<r){
    int mid=l+r>>1;if(check(mid)) r=mid;else l=mid+1;}cout<<r<<endl;return 0;
}