[JOISC 2021 Day2] 道路の建設案 (Road Construction) 解题报告

· · 题解

看到题解区都是双 \log 的做法，我提供一种单 \log 的做法。

为了方便，我们先曼哈顿距离转切比雪夫距离。

看到了第 k 大，我们考虑二分答案，考虑如何判断是否合法。

这里我们采取对平面进行分块，假设当前二分的答案为 d，我们就每 d 个分成一块。

如何统计答案呢？考虑到直接对于当前点所在的块以及相关的八个方向爆枚一通。

可以证明，这样的复杂度是 O(n) 的。

所以总复杂度 O(n\log a)。

不过常数太大了，所以跑得跟两个 \log 估计也差不多。

#include<cstdio>
#include<algorithm>
#include<unordered_map>
#include<vector>
#define ll long long
#define pir pair<ll,ll>
using namespace std;
const int N=5e5+10,P=1e7+7;
vector<pir> v[N];
namespace ht
{
    struct edge{
        int next;
        ll x,y;
    }e[N];
    int first[P],len,q[N],cnt;
    int qry(ll x,ll y,bool p)
    {
        int w=(x*1919+y*811)%P;
        if(w<0) w+=P;
        for(int i=first[w];i;i=e[i].next)
            if(e[i].x==x&&e[i].y==y) return i;
        if(!p) return -1;
        e[++len]=edge{first[w],x,y};
        if(!first[w]) q[++cnt]=w;
        first[w]=len;
        return len;
    }
    void clear()
    {
        for(int i=1;i<=len;i++) v[i].clear();
        for(int i=1;i<=cnt;i++) first[q[i]]=0;
        len=cnt=0;
    }
}
int len,k,p,n;
ll ans[N<<2];
ll calc(ll a,ll b)
{
    if(a>=0) return a/b;
    else return (a+1)/b-1;
}
void push(ll x)
{
    ans[++len]=x;
}
void work(ll d,ll x,ll y,int i)
{
    if(i<0) return;
    if(len>=k&&p) return;
    ll w;
    for(pir a:v[i])
    {
        w=max(abs(a.first-x),abs(a.second-y));
        if(w<=d) push(w);
    }
}
const int f1[10]={0,1,1,1,0,-1,-1,-1,0},f2[10]={0,1,0,-1,-1,-1,0,1,1};
ll x[N],y[N],a,b;
bool chk(ll d)
{
    ht::clear(),len=0;
    for(int i=1;i<=n;i++)
    {
        a=calc(x[i],d),b=calc(y[i],d);
        for(int k=0;k<9;k++)
            work(d,x[i],y[i],ht::qry(a+f1[k],b+f2[k],0));
        v[ht::qry(a,b,1)].push_back({x[i],y[i]});
        if(p&&len>=k) return 1;
    }
    return 0;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&a,&b),x[i]=a+b,y[i]=a-b;
    ll l=1,r=4e9,mid;
    p=1;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(chk(mid)) r=mid;
        else l=mid+1;
    }
    chk(l);
    sort(ans+1,ans+len+1);
    for(int i=1;i<=k;i++)
        printf("%lld\n",ans[i]);
}