解法:二分 + 扫描线
二分答案,每次做扫描线,$Nlog^2{M}$ N是点的个数,M是坐标范围,跑得很快
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define ls(x) (x << 1)
#define rs(x) ((x << 1) + 1)
int n, C;
pii a[505];
struct Node{
int l,r,dat,mk;
#define l(x) t[x].l
#define r(x) t[x].r
#define dat(x) t[x].dat
#define mk(x) t[x].mk
}t[40004];
void build(int p, int l, int r)
{
l(p) = l; r(p)= r;
if(l == r) {dat(p) = 0, mk(p) = 0; return;}
int mid = (l + r) >> 1;
build(ls(p), l, mid);
build(rs(p), mid + 1, r);
dat(p) = 0; mk(p) = 0;
}
void spr(int p)
{
if(mk(p))
{
dat(ls(p)) += mk(p);
dat(rs(p)) += mk(p);
mk(ls(p)) += mk(p);
mk(rs(p)) += mk(p);
mk(p) = 0;
}
}
void update(int p, int l, int r, int v)
{
if(l <= l(p) && r >= r(p))
{
dat(p) += v;
mk(p) += v;
return;
}
spr(p);
int mid = (l(p) + r(p)) >> 1;
if(l <= mid) update(ls(p), l, r, v);
if(r > mid) update(rs(p), l, r, v);
dat(p) = max(dat(ls(p)), dat(rs(p)));
}
int ask()
{
return dat(1);
}
int main()
{
cin >> C >> n;
for(int i = 1; i <= n; i++)
{
cin >> a[i].first >> a[i].second;
}
int l = 1, r = 10000;
while(l < r)
{
build(1, 1, 10001);
vector<pair<int,pair<int,pii> > > q;
int mid = (l + r) >> 1;
for(int i = 1; i <= n; i++)
{
int x = a[i].first, y = a[i].second;
x ++ ,y ++ ;
q.push_back({x, {1, {y, y + mid - 1}}});
q.push_back({x + mid, {-1, {y, y + mid - 1}}});
}
sort(q.begin(), q.end());
int flag = 0;
for(int i = 0; i < q.size(); i++)
{
pii tt = q[i].second.second;
int w = q[i].second.first;
update(1, tt.first, tt.second, w);
if(ask() >= C)
{
flag = 1;
break;
}
}
if(flag) r = mid;
else l = mid + 1;
}
cout << l;
}