555 div3 E. Minimum Array *

　　题意：给出两个长度为n数字串 ab 数字范围为0-n-1

可以任意改变b 的位置  求

（ai+bi)%n的字典序最小

压4ms过的。。。

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define pb push_back
#define CLR(A,v)  memset(A,v,sizeof A)
//////////////////////////////////
#define inf 0x3f3f3f3f
const int N=2e5+5;
const int M=1000;
int a[N],b[N];
vector<int>table;
int cnt[N];
vector<int>ans;
int main()
{
    int n;RI(n);
    rep(i,1,n)
    RI(a[i]);
    rep(i,1,n)
    RI(b[i]),cnt[b[i]]++;

    rep(i,0,n-1)
    if(cnt[i])table.pb(i);
    vector<int>::iterator it;

    rep(i,1,n)
    {
        int minn=table[0],minn2;
        it=lower_bound(table.begin(),table.end(),n-a[i]);
        if(it==table.end())
        {
            ans.push_back( (a[i]+minn)%n);
            if(--cnt[minn]==0)table.erase(table.begin());
        }
        else
        {
            if( (a[i]+minn)%n<(a[i]+*it)%n )
            {
                ans.push_back( (a[i]+minn)%n);
                if(--cnt[minn]==0)table.erase(table.begin());
            }
            else
            {
                ans.push_back((a[i]+*it)%n);
                if(--cnt[*it]==0)table.erase(it);
            }
        }
    }
    rep(i,0,n-1)
    {
        if(i!=0)cout<<" ";
        cout<<ans[i];
    }

    return 0;
}

 大神的并查集

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
typedef long long LL;

const int MAX_N=2e5+5;
int n,m,T;
int a[MAX_N],b[MAX_N];
vector<int> ive;
int id[MAX_N];
int res[MAX_N];

int Find(int x){
    if(id[x]!=x)    id[x]=Find(id[x]);
    return id[x]; 
}
Union(int a,int b){
    id[Find(a)]=Find(b);
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;++i)
        scanf("%d",&a[i]);
    int x;
    for(int i=0;i<n;++i)
    {
        scanf("%d",&x);
        ++b[x];    id[i]=i;
    }
    id[n]=0;
    for(int i=0;i<n;++i)
        if(!b[i])    Union(i,i+1);
    for(int i=0;i<n;++i)
    {
        x=Find(n-a[i]);
        res[i]=(a[i]+x)%n;
        --b[x];
        if(!b[x])    Union(x,x+1);
    }
    for(int i=0;i<n-1;++i)
        printf("%d ",res[i]);
    printf("%d
",res[n-1]);
    
    return 0;
}

官方题解：  

用了重集set

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif
    
    int n;
    cin >> n;
    vector<int> a(n);
    multiset<int> b;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        b.insert(x);
    }
    
    for (int i = 0; i < n; ++i) {
        auto it = b.lower_bound(n - a[i]);
        if (it == b.end()) it = b.begin();
        cout << (a[i] + *it) % n << " ";
        b.erase(it);
    }
    cout << endl;
    
    return 0;
}