赶牛入圈
题目 赶牛入圈
思路分析
模型可以抽象成：
要找到最小的一个方框 让它里面包含C个草
我们怎么快速得知一个方框里有几个草呢？
很明显 二维前缀和 利用\(s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]\)就能求出来
那么我们就把所有的草 构造出一个前缀和数组
但是发现
范围在1~10000之间 这要构造的话 就得\(10000^2\)显然不行
而点的范围只有500 （只有\(500^2\)个草）
那么我们就可以使用离散化 把这500个有意义的数据映射在一个小的二维数组里面
再对这个新数组进行前缀和操作
对于找到最小边长 看到关键词最小 不难想到用二分去找答案
给定一个mid边长 去前缀和数组中以这个大小遍历一遍 看是否有满足条件的（有C个草）
如果有 说明我们这个mid可能取大了 也可能刚好取到 所以r=mid
如果没有 说明 mid取小了 l=mid+1 所以为模版1
这个边长不外乎就是取大了取小了 显然具有二段性 所以二分是可行的
这个check中的遍历过程 实际上是用到了双指针 右边和下面（x2和y2）不断右探 当不满足条件时（x2到x1的距离大于给定的mid长度时）x1、y1才++ 这里有个注意点就是 我们用的是离散化后的点算距离 所以x2和x1 y2和y1之间的距离不是x2-x1和y2-y1 而是我们真实数组里面的距离 需要用alls[x2]-alls[x1+1]+1 和alls[y2]-alls[y1+1]+1来算
有三个问题 依次来进行解释
首先为什么用alls
离散化后是把两个有意义的点映射在新下标处 他们真实的距离可并不是新下标去做减法计算 而是要用离散化前的真实数组的下标去做计算 而真实下标存在哪里呢 对 在alls里面
第二 为什么用alls[x2]-alls[x1+1]+1 和alls[y2]-alls[y1+1]+1 这里要加上个1？
这是双指针尺取法的一个细节问题 意思是 如果我下一个点不满足状态了 我就要更新左边的指针了 而不是我已经不满足了才更新 具体了解 去刷双指针
第三 为什么用alls[x2]-alls[x1+1]+1 和alls[y2]-alls[y1+1]+1 这里又要加1？
不妨转为一维来看
因为草不是一个点 而是一个块 它是有单位长度的
所以要把x1包含进来 应该还得加上个1
最后回过头来考虑判定问题
一个范围里是否有≥C个草 满足true 否则false
既然前面有边界细节要扣 这里应该也有
还是如上图所示 要包含x1这块草 得加1
所以对于原公式的\(s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]\)
y1-1和x1-1是完全没必要的
因为x1 y1本身就没取到那一块
所以公式变成 \(if(s[x2][y2]-s[x1][y2]-s[x2][y1]+s[x1][y1]>=C)\)
这样一来这道题就解决了
会发现涉及的东西真多啊 二维前缀和 二分 离散化 双指针 枚举……虽然也都是基本功
还有一大堆细节要扣
真的好 这题（但别出现在赛场上 hh）
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef pair<int,int> PII;
const int N=1010;
PII point[N];
vector<int> alls;
int s[N][N];
int n,C;
int find(int k){
int l=0,r=alls.size()-1;
while(l<r){
int mid=l+r>>1;
if(alls[mid]>=k) r=mid;
else l=mid+1;
}
return r;
}
bool check(int len){
for(int x1=0,x2=1;x2<alls.size();x2++){
while(alls[x2]-alls[x1+1]+1>len)
x1++;
for(int y1=0,y2=1;y2<alls.size();y2++){
while(alls[y2]-alls[y1+1]+1>len)
y1++;
if(s[x2][y2]-s[x1][y2]-s[x2][y1]+s[x1][y1]>=C)
return true;
}
}
return false;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>C>>n;
alls.push_back(0);//为了从1开始做前缀和 先放个0占位
for(int i=0;i<n;i++){
int x,y;cin>>x>>y;
point[i]={x,y};
alls.push_back(x);
alls.push_back(y);
}
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
for(int i=0;i<n;i++){
int x=find(point[i].first),y=find(point[i].second);
s[x][y]++;
}
for(int i=1;i<alls.size();i++){
for(int j=1;j<alls.size();j++){
s[i][j]+=s[i-1][j]+s[i][j-1]-s[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;
}
💬 评论