Chef Sereja and Sorting 2
我的想法是：先排序，从开头到结尾不断找到对应位置的值，交换。那么l位置就是已经排好序的了。只有0.67分优化了下find() 0.725
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=10002;
int n,a,b,left,right;
int find(int b,int val){
if(a==val) return b;
for(int i=n;i>b;i--)
if(a==val)
return i;
}
void swap(int l,int r){
while(l<r){
int t=a;
a=a;
a=t;
l++,r--;
}
}
int main(){
while(~scanf("%d",&n)){
for(int i=1;i<=n;i++){
scanf("%d",a+i);
b=a;
}
sort(b+1,b+n+1);
int cnt=0,l=1,r=1;
for(int i=1;i<=n;i++){
r=find(l,b);
if(r>l){
left=l;
right=r;
swap(l,r);
cnt++;
}
l++;
}
printf("%d\n",cnt);
for(int i=0;i<cnt;i++)
printf("%d %d\n",left,right);
}
return 0;
}
页:
[1]