题解 CF1375E 【Inversion SwapSort】

sry_ · 2020-12-24 13:46:00 · 题解

为啥现在假做法一直过题啊！

有一个不知道对不对的做法，考虑当前序列 A 中若没有 i 使得 A_i> A_{i+1} 那么肯定 A 是不严格单调递增的。

否则我们将 i 与 i+1 对应的原 A 的下标翻转，最后倒叙输出即可。

正确性未知，但交了一发就过了？？？

#include<iostream>
#include<cstring>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<queue>
#include<vector>
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
using namespace std;
inline int read(){
    int f=1,ans=0; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
const int MAXN=1e3+11;
int N,A[MAXN],id[MAXN]; vector<pii> vec,Ans;
int main(){
    N=read(); for(int i=1;i<=N;i++) A[i]=read(),id[i]=i;
    for(int i=1;i<=N;i++) for(int j=i+1;j<=N;j++) if(A[i]>A[j]) vec.pb(mp(i,j));
    while(1){
        int ps=-1; for(int i=1;i<N;i++) if(A[i]>A[i+1]){ps=i;break;}
        if(ps==-1) break; Ans.pb(mp(id[ps],id[ps+1])); swap(A[ps],A[ps+1]); swap(id[ps],id[ps+1]);
    }
    printf("%ld\n",Ans.size()); for(int i=Ans.size()-1;i>=0;i--) printf("%d %d\n",Ans[i].fi,Ans[i].se);
    return 0;
    //for(auto v:Ans) printf("%d %d\n",v.fi,v.se);return 0;
}