Hash Function(并查集贪心/线段树建边)

题目链接

https://ac.nowcoder.com/acm/contest/142/J?&headNav=acm&headNav=acm

题目大意

给出线性哈希后的哈希数组,问字典序最小的插入顺序是什么。

解题思路

解法一:并查集贪心

最开始的时候,我们第一次插入显然只能从那些a[i]%n==i的数中选择,第二次只能从除了刚才用掉的那个数之外的数和a[i+1]中进行选择,后面的操作同理,因为要求字典序最小,所以每次选择插入的一定是可以选择的最小的哪一个数。
因此我们用优先队列维护一个可选择的集合,对于每个点,我们维护它在当前插入过程中左右两边连续的最左最右端点,然后将右端点后的第一个加入可选择的优先队列中,然后按照上面说的循环操作即可。

代码

#include <bits/stdc++.h>
const int maxn=2e5+100;
typedef long long ll;
using namespace std;
int n,num;
int a[maxn],b[maxn],vis[maxn],l[maxn],r[maxn];
vector<int>ans;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
int findr(int pos){
    int ans=r[pos]+1;
    if(ans==n){
        if(b[0]!=-1)ans=r[0]+1;
        else ans=0;
    }
    return ans;
}
void init(){
    ans.clear();
    num=0;
    for(int i=0;i<=n;i++){
        vis[i]=0;
        l[i]=r[i]=i;
        b[i]=-1;
    }
}
void solve(){
    for(int i=0;i<n;i++){
        if(a[i]==-1)continue;
        num++;
        if(a[i]%n==i){
            q.push(make_pair(a[i],i));
            vis[i]=1;
        }
    }
    while(!q.empty()){
        pair<int,int> dd=q.top();
        q.pop();
        int x=dd.first;
        int pos=dd.second;
        ans.push_back(x);
        b[pos]=x;
        if(pos-1>=0&&b[pos-1]!=-1)
        {
            l[pos]=l[pos-1];
            r[l[pos-1]]=r[pos];
        }
        if(pos+1<n&&b[pos+1]!=-1)
        {
            r[pos]=r[pos+1];
            r[l[pos]]=r[pos+1];
            l[r[pos+1]]=l[pos];
        }
        int rpos=findr(pos);
        if(rpos<0||rpos>=n)continue;
        if(a[rpos]==-1)continue;
        if(vis[rpos])continue;
        int y=a[rpos];
        int yy=y%n;
        if((yy>=l[pos]&&yy<=r[pos])||(l[pos]==0&&b[n-1]!=-1&&yy>=l[n-1]&&yy<=r[n-1])){
           q.push(make_pair(y,rpos));
           vis[rpos]=1;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        init();
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        solve();
        if((int)ans.size()!=num){
            cout<<"-1"<<endl;
            continue;
        }
        for(int out:ans){
            cout<<out<<" ";
        }
        cout<<endl;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注