题解：P10466 邻值查找

MoCaRabbit · 2024-05-17 21:51:08 · 题解

投一波 Hash + 链表。

这是一种离线做法。

先观察，1 \le j <i。

那么，离线之后倒序处理最好了。

先对 a_i 排序。

再按排序的顺序插入链表。

让 i 从 n 枚举到 2。

每次从链表里删去在原序列排名为 i 的数，在删除前看下自己两边的数，哪个离 a_i 的值较近，就取哪个。

这样能求出所需的答案。

找在原序列排名为 i 的数可以用 Hash 记录。

其他都用链表 O(1) 完成。

这样就可以很好的用链表的性质。

加个小基数排序，理论 O(n) 解决。

接着，一首小诗献上。

我爱 STL。

他给我了常数。

他给了我码疯。

但是。

他还给了我便捷。

他还给了我码短。

有时候，明知常数大，却要去图方便。

有时候，明知代码乱，却要去压码长。

啊！万恶的 STL。

请大家配着代码自行体会。

致管理，这只是在说明 STL 用多了的后果。

#include<bits/stdc++.h>
using namespace std;
list<int>s;//STL发癫之作
int n,a[int(1e5)+10],b[int(1e5)+10];
int buc[310],c[int(1e5)+10];
void radix_sort(int a[],int l,int r){
    for(int i=l;i<=r;i++) a[i]+=1e9;
    int radix=0;
    for(int i=1;i<=4;i++){
        memset(buc,0,sizeof buc);
        for(int j=l;j<=r;j++) buc[(a[j]>>radix)&255]++;
        for(int j=0;j<256;j++) buc[j]+=buc[j-1];
        for(int j=r;j>=l;j--) c[l+(buc[(a[j]>>radix)&255]--)-1]=a[j];
        for(int j=l;j<=r;j++) a[j]=c[j];
        radix+=8;
    }
    for(int i=l;i<=r;i++) a[i]-=1e9;
}
unordered_map<int,int>mp;
unordered_map<int,list<int>::iterator>pos;
stack<pair<int,int> >st;
int main() {
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i];
        mp[a[i]]=i;
    }
    radix_sort(a,1,n);
    for(int i=1;i<=n;i++){
        s.push_back(a[i]);
        pos[a[i]]=prev(s.end());
    }
    for(int i=n;i>1;i--){
        list<int>::iterator it=pos[b[i]];
        int t1=2e9,t2=2e9;
        if(next(it)!=s.end()) t1=*next(it);
        if(it!=s.begin()) t2=*prev(it);
        int ans;
        if(t2==2e9) ans=t1;
        else if(t1==2e9) ans=t2;
        else if(abs(t1-*it)==abs(t2-*it))
            ans=t2;
        else if(abs(t1-*it)<abs(t2-*it))
            ans=t1;
        else ans=t2;
        st.push({abs(ans-*it),mp[ans]});
        s.erase(it);
    }
    while(!st.empty()) cout<<st.top().first<<" "<<st.top().second<<"\n",st.pop();
    return 0;
}

TM 的，一个 O(n) 的连 O(n\log n) 平衡树都跑不过。