AcWing 121. 赶牛入圈
原题链接
中等
作者:
开心小子
,
2019-09-21 22:27:25
,
所有人可见
,
阅读 888
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=1010;//离散化之后最多有1000个不同的数
vector<int > numbers;//存储需要离散化的数
//注意横纵坐标的值要一块离散化,所以最多有1000个
int sum[maxn][maxn];
typedef pair<int ,int > PII;
PII points[maxn];//存储每个点的坐标
int C,n;
int get(int x)
{
int l=0,r=numbers.size()-1;//已知离散化的最大范围
//注意 离散化的位置是从1开始的
//因为已经提前放入了0元素
while(l<r)
{
int mid=l+r>>1;
if(numbers[mid]>=x)r=mid;
else l=mid+1;
}
//利用二分法查找x元素在离散化容器中的位置
//即将元素离散化数据的位置
return r;
}
bool check(int len)
{
//查找len长度的正方形是否能装下C颗草
for(int x1=0,x2=1;x2<numbers.size();x2++)
{
//在一维上查找横轴上是否满足条件
//先解释numbers[x2]-numbers[x1+1]>len的部分是,找到最后一个x1'使得numbers[x2]-numbers[x1']<len,这时我们返回x1'-1=x1
//在解释这里为什么要加1,首先根据题意,每颗草是在一个1*1的正方形中的而不是一个点
//这样我们虽然获得的是x1~x2之间的距离,但在某一端的1单位的边长是没有算进来的所以这里要加上1
while(numbers[x2]-numbers[x1+1]+1>len)x1++;
for(int y1=0,y2=1;y2<numbers.size();y2++)
{
while(numbers[y2]-numbers[y1+1]+1>len)y1++;
if(sum[x2][y2]-sum[x1][y2]-sum[x2][y1]+sum[x1][y1]>=C)
return true;
}
}
return false;
}
int main(){
ios::sync_with_stdio(false);
cin>>C>>n;
numbers.push_back(0);
for(int i=0;i<n;i++)
{
int x,y;
cin>>x>>y;
points[i]={x,y};
numbers.push_back(x);
numbers.push_back(y);//将横纵坐标存储到容器中等待处理
}
sort(numbers.begin(),numbers.end());
numbers.erase(unique(numbers.begin(),numbers.end()),numbers.end());
//该语句的作用是将重复的元素删除
//unique(number.begin(),numbers.end()) 是在整体中搜索一旦发现重复的元素就放到最后
//然后返回第一个重复元素的迭代器,这样就能在利用erase()起到删除重复元素的作用
for(int i=0;i<n;i++)
{
int x=get(points[i].first),y=get(points[i].second);
sum[x][y]++;
//利用get函数离散化并将离散化的点放入前缀和数组中
}
for(int i=1;i<numbers.size();i++)
{
for(int j=1;j<numbers.size();j++)
{
sum[i][j]+=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
}
}
int l=1,r=10000;
while(l<r)
{
int mid=l+r>>1;
if(check(mid))r=mid;
else l=mid+1;
}
cout<<r<<endl;
return 0;
}