CodeForces 362C

分析：首先我们要知道调用swap()函数的次数跟什么有关。可以观察发现在Insertion Sort里，当且仅当a[j](j∈[0,i)) > a[i]时会调用一次swap()，也就是说有多少个a[j](j∈[0,i)) > a[i]成立就会调用多少次swap()（因为a[i]前面的序列都是有序的），这个数目也叫逆序数。所以要使调用swap()的次数最少，就应该要使整个序列的总的逆序数最小。这时，我们可以枚举所有不同的两个位置对换之后的总逆序数来找最小的总逆序数。但枚举的时候我们需要知道a[i]与a[j]对换之后各自的逆序数以及对换之前的逆序数，记为b[i][j]、b[j][i]、b[i][i]、b[j][j]。因为我们对换a[i]和a[j]的行为只会影响到i~j上的元素的逆序数，我们可以用b[i][j]、b[j][i]、b[i][i]、b[j][j]推导出对换之后的总逆序数的增量。只要求出这个最小的增量我们就可以求得最小的总逆序数。

那现在的关键就是比较快的求出数组b的所有元素的值。这个可以在O(n^2)的时间内完成。在n <= 5000的条件下应该还是可以接受的。

这道题花了不少时间，主要原因在于没把推导的公式写得清清楚楚，虽然知道推导公式的方法，但是没有很快的推出正确的公式。

 #include <iostream>

 #include <queue>

 #include <string>

 #include <cstring>

 #include <algorithm>

 #include <cstdio>

 #include <map>

 #include <vector>

 using namespace std;

 int a[], b[][], n;

 int main(){

     cin >> n;

     for (int i = ; i < n; i++){

         cin >> a[i];

     }

     for (int i = ; i < n; i++){

         for (int j = ; j < n; j++){

             b[i][j] = -;

         }

     }

     for (int i = ; i < n; i++){

         b[i][] = ;

         for (int j = ; j < i; j++){

             if (a[i] < a[j]){

                 b[i][j + ] = b[i][j] + ;

             }else{

                 b[i][j + ] = b[i][j];

             }

         }

         for(int j = i + ;j < n;j++){

             if(a[i] < a[j]){

                 b[i][j] = b[i][j - ] + ;

             }else{

                 b[i][j] = b[i][j - ];

             }

         }

     }

     int ans = ;

     map<int,int> m;

     for (int i = ; i < n; i++){

         for (int j = i + ; j < n; j++){

             int x =  * (b[i][j] - b[i][i] + b[j][i] - b[j][j]) - (a[i] < a[j]?:) + (a[i] > a[j]?:);

             m[x]++;

             ans = min(ans,x);

         }

     }

     int counter = ;

     for (int i = ; i < n; i++){

         int j = i;

         while (j >  && a[j] < a[j - ])

         {

             swap(a[j], a[j - ]); // swap elements a[j] and a[j - 1]

             counter++;

             j = j - ;

         }

     }

     cout << counter + ans << " " << m[ans] << endl;

     return ;

 }

巴特西

CodeForces 362C

最新文章

热门文章