cf-362C-Insertion Sort - c++编程基础

题意：

已知一个无序的序列，使用冒泡排序对其进行排序，需要进行一定的SWAP（）操作次数。

现在，让你从这个序列任意选择两个数进行交换，交换后再进行冒泡排序，使得交换后进行的冒泡排序中SWAP的操作

尽可能的少。

样例1解析：

4 0 3 1 2进行冒泡排序需要进行6次SWAP操作。

如果交换4,2，那么2 0 3 1 4只需要进行3次SWAP操作。

交换4,1，那么1 0 3 4 2也只需要进行3次SWAP操作。

交换之后需要进行3次SWAP操作，一共有2种交换方式，所以输出3 2.

做法：

num[i][j]=k:对于元素i，数组位于j后的所有元素，有k个小于i的数

然后枚举交换任意两个元素，SWAP的操作次数.

sum代表未交换元素时，SWAP的操作次数。

对于交换第i个和第j个元素（i>j,a[i]

int aa,bb,cc,dd,ns;

aa=num[a[i]][j]-num[a[i]][i];

dd=num[a[j]][j]-num[a[j]][i];

bb=dd-aa;

cc=(i-j-1)-dd;

ns=sum+aa-bb-(dd+1);

aa代表从i到j，比a[i]小的数的个数

bb代表从i到j，比a[i]大，比a[j]小的数的个数

cc代表从i到j，比a[j]大的数的个数

ns代表交换元素i，j后，再进行冒泡排序，SWAP的次数

#include  
#include  
#include  
using namespace std;  
int a[5001];  
int wei[5001];  
int num[5001][5001];  
int main()  
{  
    int n,i,j;  
    scanf("%d",&n);  
    for(i=0; i=0;j--)  
        {  
            if(a[j]a[j])continue;  
            int aa,bb,cc,dd,ns;  
            aa=num[a[i]][j]-num[a[i]][i];  
            dd=num[a[j]][j]-num[a[j]][i];  
            bb=dd-aa;  
            cc=(i-j-1)-dd;  
            ns=sum+aa-bb-(dd+1);  
            if(ns