1930. 排序

Constraints

Time Limit: 1 secs, Memory Limit: 32 MB

Description

我们都知道，在排序算法中需要进行多次比较。若比较的两个数Ai, Aj(i<j)，Ai>Aj的话，则称作有效比较。给定一个有N个互异元素的整数序列，请使用选择排序对序列进行排序，并输出其有效比较次数。这里假设使用的是标准的排序算法，并且从下标小到大的顺序进行枚举。
比如，给定序列[4,1,3,2]，选择排序的有效比较按顺序有(4,1), (4,3), (3,2)。

Input

 第一行为一个整数t，表示测试用例个数。对于每个测试用例，第一行包含一个整数n（0<n<100），表示序列的元素个数。接下来一行包含n个互不相同的整数，表示序列的元素。

Output

为每个测试用例单独输出一行表示使用标准的选择排序的有效比较次数。 

Sample Input

2
4
4 1 3 2
3
3 2 1

Sample Output

3
2

// Problem#: 1930
// Submission#: 1995867
// The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
// URI: http://creativecommons.org/licenses/by-nc-sa/3.0/
// All Copyright reserved by Informatic Lab of Sun Yat-sen University
#include<iostream>
#include<string>
using namespace std;


 int main(){
  int t;
  cin>>t;
  while(t--){
      int n;
      cin>>n;
      int *p=new int[n];
      int i;
      for(i=0;i<n;i++){
          cin>>p[i];
      }
      int counter=0;
      int key;
      for(i=0;i<n-1;i++){
          int flag=i;
          for(key=i+1;key<n;key++){
              if(p[key]<p[flag]){
                  flag=key;
                  counter++;
              }
          }
          if(flag!=i){
              int temp=p[i];
              p[i]=p[flag];
              p[flag]=temp;
          }
      }
      cout<<counter<<endl;
  }
  return 0;
}