csuoj 1352: New Sorting Algorithm

因为每个元素都是移动到比它小1位的元素的后面；

这样的话以后的一定就可以把他们两个打包；

所以用这种方法最多扫一遍就可以了；

但是最小的那个数要不要移动呢？

如果最小的数后面的数都是升序的，那么一直扫到最小的那个数就行了；

不然的话要完整的扫一遍；

这个地方我没想清楚，WA的好惨，最后还是看到斌哥的代码才恍然大悟的；

#include<cstdio>

#include<algorithm>

#define maxn 100005

using namespace std;

int n,t,m;

int num[maxn],f[maxn],r[maxn],cnt[maxn];

bool cmp(const int &x,const int &y)

{

    return num[x]<num[y];

}

int find(int x)

{

    return f[x]==x?x:f[x]=find(f[x]);

}

void merge(int x,int y)

{

    int xx=find(x);

    int yy=find(y);

    if(xx!=yy)f[yy]=xx,cnt[xx]+=cnt[yy];

}

void pre()

{

    for(int i=; i<=n; i++)r[i]=i;

    sort(r+,r+n+,cmp);

    for(int i=; i<=n; i++)num[r[i]]=i;

    for(int i=; i<=n; i++)f[i]=i,cnt[i]=;

}

void solve()

{

    long long ans=;

    bool flag=;

    for(int i=r[]; i<n; i++)

        if(num[i]>num[i+])

        {

            flag=;

            break;

        }

    if(flag)m=r[]-;

    else m=n;

    for(int i=; i<=m; i++)

    {

        int v=num[i];

        ans+=cnt[v];

        merge(v-,v);

    }

    printf("%lld\n",ans);

}

int main()

{

//    freopen("test0.in","r",stdin);

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        for(int i=; i<=n; i++)

            scanf("%d",&num[i]);

        pre();

        solve();

    }

    return ;

}