题解 CF109D 【Lucky Sorting】

· · 题解

将这个序列变成最终序列。

77 66 55 44 33 22 11
11 22 33 44 55 66 77

可以形成一些闭环。

77-11
66-22
55-33
44

当我们要 swap(i,j) 但他们都不是幸运数时，我们使用一个中介数 k 。

swap(i,k) 现在 i 里装的是 k 的灵魂。

swap(i,j) i 里 j 的灵魂， j 里 k 的灵魂。

swap(j,k) 最后换了回去。

我们先将你选择的作为整个过程的中介数的幸运数所在闭环给解决掉。（挨个换）

然后再把中介数和另一个闭环的头 swap 然后像处理幸运数所在闭环时一样处理，最后再换回来即可。

我的中介数选择的是最小的幸运数。代码可能有点细节。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,tot,vis[N],bg[N],b[N],ok[N];
vector<pair<int,int> >ans;
struct node{
    int id,val,fl,mb;
}a[N<<1];
bool check(int x){
    while(x>0){
        if(x%10!=4&&x%10!=7) return 0;
        x/=10;
    }
    return 1;
}
bool cmp(int x,int y){
    return a[x].val<a[y].val;
}
void print(int x,int y){
    if(x>y) swap(x,y);
    if(x!=y) ans.push_back(make_pair(x,y));
}
void work(int x){
    bg[++tot]=x;
   // cout<<x;
    int nw=a[x].mb; vis[nw]=tot;
    while(nw!=x){
  //      cout<<"-"<<nw;
        nw=a[nw].mb; vis[nw]=tot;
    }
   // cout<<endl;
    return;
}
void solve(int bh,int k){
    //a[k] 与头交换
    ok[bh]=1;
   // cout<<"*"<<bh<<" "<<bg[bh]<<endl;
    print(k,bg[bh]);
    int i=bg[bh];
    while(a[i].mb!=bg[bh]){
        //cout<<"i: "<<i<<" "<<a[i].mb<<endl;
        print(i,a[i].mb);
        i=a[i].mb;
    }
    print(k,i);
}
int main(){
    scanf("%d",&n);
    bool flg=1; int k=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i].val);
        a[i].id=i; b[i]=i;
        if(check(a[i].val)) {
            a[i].fl=1;
            if(a[i].val<a[k].val||k==0) k=a[i].id;
        }
        if(i>1&&a[i-1].val>a[i].val) flg=0;
    }
    if(flg){ puts("0"); return 0; }
    if(k==0) { puts("-1"); return 0; }
    sort(b+1,b+n+1,cmp);
    for(int i=1;i<=n;i++) a[i].mb=b[i];//,cout<<"*"<<b[i]<<" "<<i<<endl;
    for(int i=1;i<=n;i++)
        if(!vis[i]) work(i);

    ok[vis[k]]=1;
    //操作数所在环，先用操作数搞好。
  //  cout<<a[k].val<<" "<<"***"<<endl;
    int i=k;
    while(a[i].mb!=k){
       // cout<<i<<endl;
        print(i,a[i].mb);
        i=a[i].mb;
    }
    k=i; //操作数来到目标位置

 //   cout<<"***"<<ans.size()<<endl;
    //其他环
    for(int i=1;i<=tot;i++)
        if(!ok[i]) solve(i,k);
    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++)
        printf("%d %d\n",ans[i].first,ans[i].second);
    return 0;
}

（趁估值掉完之前水一发cf题解）