题目
原题链接
问题描述
分析
先考虑直观思路,使用二维前缀和,再二分边长,但是在二维前缀和这一步就会导致时间空间的双爆炸,根据观察,发现数据只有500个,所以可以考虑离散化。
但这里的特别之处是这里是一个二维平面,所以我们的问题是如何对二维平面中的点进行离散化以及如何使用离散化的结果来判断边长是否满足要求。
二维离散化

如果一个点之前的坐标是 [ a [ i ] . x , a [ i ] . y ] [a[i].x,a[i].y] [a[i].x,a[i].y],那么将其映射到二维离散化平面的结果也就是其横纵坐标各自离散化的值,这样我们就保证了相对关系没有发生变化。
判断边长是否满足要求
给定边长大小,
如果采用的是一个直接的二维前缀和平面,我们需要枚举出每一个满足要求的点,这样会让时间空间爆炸;
如果是一个离散化的二维平面,我们只需要枚举上面满足要求的点集,同时满足时间空间要求。
代码
#include <bits/stdc++.h> typedef long long ll; using namespace std; #define fir(i, a, b) for (ll i = (a); i <= (b); i++) #define rif(i, a, b) for (ll i = (a); i >= (b); i--) const int N=5e2+5; const ll mod=; ll c,n,s[N][N],sz_x,sz_y; struct node{
ll x,y; }; ll cmp1(node a,node b){
return a.x<b.x;} ll cmp2(node a,node b){
return a.y<b.y;} node a[N]; map<ll,ll>mpx,mpy; vector<ll>vx,vy; bool check(ll tmp){
//在二维离散化结果中,使用双指针扫描 for (int i = 1, k = 0; i <= sz_x; ++ i ) if (vx[i] - vx[1] + 1 >= tmp || i == sz_x){
while (vx[i] - vx[k+1] + 1 > tmp) k ++;//双指针扫描合法区间 for (int j = 1, g = 0; j <= sz_y; ++ j ) if (vy[j] - vy[1] + 1 >= tmp || j == sz_y) {
while (vy[j] - vy[g+1] + 1 > tmp) g ++; if (s[i][j] - s[i][g] - s[k][j] + s[k][g] >= c) return true; } } return false; } inline void solve(){
vx.push_back(0); vy.push_back(0); cin>>c>>n; fir(i,1,n){
cin>>a[i].x>>a[i].y; } //二维离散化(不破坏相对位置) sort(a+1,a+n+1,cmp1); fir(i,1,n){
if(!mpx[a[i].x]){
vx.push_back(a[i].x); mpx[a[i].x]=vx.size()-1; } } sort(a+1,a+n+1,cmp2); fir(i,1,n){
if(!mpy[a[i].y]){
vy.push_back(a[i].y); mpy[a[i].y]=vy.size()-1; } } fir(i,1,n){
s[mpx[a[i].x]][mpy[a[i].y]]++; } sz_x=vx.size()-1,sz_y=vy.size()-1; fir(i,1,sz_x){
fir(j,1,sz_y){
s[i][j]+=s[i][j-1]+s[i-1][j]-s[i-1][j-1]; } } ll l=1,r=10000,mid; while(l<r){
mid=(l+r)>>1; if(check(mid))r=mid; else l=mid+1; } cout<<r<<endl; } int main(){
ll _; // cin>>_; _=1; while(_--){
solve(); } return 0; }
讯享网

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/132420.html