http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=395#problem/E

由于这道题要用到对换的数学方法,便可以用两种方法做,一个是用冒泡来模拟,一个是求序列的逆序数,我采用后者

#include<stdio.h>
int main(){
    int a[100],n,l,num;
    while(scanf("%d",&n)!=EOF){
        while(n--){
            scanf("%d",&l);
            for(int i=0;i<l;i++)
                scanf("%d",&a[i]);
            num=0;
            if(l>1)  //逆序数从第二个开始求
                for(int i=1;i<l;i++)
                    for(int j=0;j<i;j++)
                        if(a[j]>a[i])
                            num++;
            printf("Optimal train swapping takes %d swaps.\n",num);
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation