给一个序列，求最少的交换次数使其有序。
排序后求置换群的个数，然后每个置换群要交换的最少次数是该个数-1，所以总的交换次数就是n-置换群的个数了。置换群可以O(n)里求得，这里只有3个数值，我用这三个点，建了个图。然后环的总权和就是置换群的个数了，min(map[1][2], map[2][1]) + min(map[1][3], map[3][1]) + min(map[2][3], map[3][2]) + abs(map[1][2] + map[2][1])即可。
1 #include < iostream > 2 #include < string > 3 #include < algorithm > 4 #include < string .h > 5 #include < vector > 6 #include < math.h > 7 #include < time.h > 8 #include < queue > 9 #include < set > 10 using namespace std; 11 12 const int MAX = 5 ; 13 14 int mm[MAX][MAX]; 15 int n; 16 vector < int > num; 17 vector < int > ord; 18 19 int go() 20 { 21 int res = 0 ; 22 memset(mm, 0 , sizeof (mm)); 23 sort(ord.begin(), ord.end()); 24 for ( int i = 0 ; i < ord.size(); i ++ ) 25 { 26 if (ord[i] == num[i]) res ++ ; 27 else mm[ord[i]][num[i]] ++ ; 28 } 29 res += min(mm[ 1 ][ 2 ], mm[ 2 ][ 1 ]); 30 res += min(mm[ 1 ][ 3 ], mm[ 3 ][ 1 ]); 31 res += min(mm[ 2 ][ 3 ], mm[ 3 ][ 2 ]); 32 res += abs(mm[ 1 ][ 2 ] - mm[ 2 ][ 1 ]); 33 return n - res; 34 } 35 36 int main() 37 { 38 freopen( " sort3.in " , " r " , stdin); 39 freopen( " sort3.out " , " w " , stdout); 40 41 scanf( " %d " , & n); 42 for ( int i = 0 ; i < n; i ++ ) 43 { 44 int d; 45 scanf( " %d " , & d); 46 num.push_back(d); 47 ord.push_back(d); 48 } 49 printf( " %d\n " , go()); 50 }
转载于:https://www.cnblogs.com/litstrong/archive/2010/04/21/1716777.html
