http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1352
题意：就是要将7 1 5 2这样的序列变成1 2 5 7最少需要多少步？给出变的规律，每次把最前面的那个数移动到比它次小的数的后面，要是它后面没有比它次小的数，就移动到最后，问最少需要多少步？
For example, we will use 7 steps to sort the sequence 7 1 5 2:
7 1 5 2 --> 1 5 7 2 --> 5 7 2 1 --> 7 2 5 1 --> 2 5 7 1 --> 5 7 1 2 --> 7 1 2 5 --> 1 2 5 7
思路：这个题目给出的数据量很大，所以一步步模拟肯定超时。那么就只能是看各种数字移动到它最终位置是否存在一定规律......经过思考，发现好像没有什么规律....于是这道题目我就放弃了.....然后我的一个队友说，一个数移动到它次小的数后面，那么就可以把这两个数合并成一个数，然后再找再合并.....这样时间复杂度会减少很多。的确是这样的，合并完之后，我们只需要用个并查集来统计有多少个数合并在一起了，然后每次移动的时候，把这些数加上即可.......只是，这样还有一个问题，如何找到比它次小的数？如果次小的数已经被合并了呢？......暴力去查找，明显耗时会很大，可能会超时，那么可以把数据进行离散化，由于所以数字都是独一无二的，那么在找次小的数的时候，我们只需要find(x-1)即可........
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
#define inf 100005
typedef long long ss;
ss father[inf],rank[inf];
ss a[inf],b[inf],n;
queue<ss>q;
queue<ss>q1;
ss erfen(ss sum)
{
ss ll=0,rr=n-1;
while(ll<=rr)
{
ss mid=(ll+rr)/2;
if(b[mid]>sum)
rr=mid-1;
else ll=mid+1;
}
return rr;
}
ss find(ss x)
{
ss i=x,root;
while(x!=father[x])
x=father[x];
root=x;
x=i;
while(x!=father[x])
{
i=father[x];
father[x]=root;
rank[root]+=rank[x];
rank[x]=0;
x=i;
}
return root;
} void liantong(ss x,ss y)
{
father[x]=y;
rank[y]+=rank[x];
rank[x]=0;
}
int main()
{
ss text;
scanf("%lld",&text);
while(text--)
{
scanf("%lld",&n);
while(!q.empty())
q.pop(); while(!q1.empty())
q1.pop();
for(ss i=0;i<n;i++)
{
scanf("%lld",&a[i]);
b[i]=a[i];
father[i]=i;
rank[i]=1;
}
sort(b,b+n);
//int ll=1,rr=n-1;
for(ss i=0;i<n;i++)
{
a[i]=erfen(a[i]);
} for(ss i=0;i<n;i++)
{
q.push(a[i]);
}
ss ans=0;
while(!q.empty())
{
ss x=q.front();
q.pop();
if(!q.empty())
{
if(x==0)
{
ss flg=0;
ss tmp=x;
while(!q.empty())
{
ss y=q.front();
if(tmp<y)
tmp=y;
else flg=1;
q.pop();
q1.push(y);
}
if(flg==1)
{
while(!q1.empty())
{
ss y=q1.front();
q1.pop();
q.push(y);
}
q.push(x);
ans+=rank[x];
}
else break;
}
else
{
ans+=rank[x];
ss y=find(x-1);
if(x!=y)
{
liantong(x,y);
}
}
}
}
printf("%lld\n",ans);
}
return 0;
}