這道題目的意思是：給你一個(gè)序列，統(tǒng)計(jì)一開始的逆序數(shù)的個(gè)數(shù)，然后依次把第一個(gè)元素放到序列末尾，求每次的逆序數(shù)個(gè)數(shù)，求出每次求逆序數(shù)里，逆序數(shù)最小的那個(gè)數(shù)

這里需要推一個(gè)遞推式，就是每次你把第一個(gè)元素放到末尾后，逆序數(shù)個(gè)數(shù)是怎么改變的 ?

　　假如第一次求出的逆序數(shù)為 a，則下次逆序數(shù)個(gè)數(shù)為 a = a + n - 2 * arr[i] - 1;我是簡(jiǎn)單的驗(yàn)證別人的結(jié)論。。。大家可以試著推下

1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 5 using namespace std; 6 7 const int MAXN = 1e5 + 10; 8 9 int main() 10 { 11 int n; 12 int i, j; 13 int arr[MAXN]; 14 while(cin >> n) 15 { 16 int sum = 0; 17 for(i = 0; i < n; ++i) 18 { 19 for(cin >> arr[i], j = 0; j < i; ++j ) 20 { 21 if(arr[i] < arr[j]) 22 sum++; 23 } 24 } 25 26 int minn = sum; 27 for(i = 0; i < n; ++i) 28 { 29 if(minn > (sum = sum+n - 2*arr[i] - 1)) 30 { 31 minn = sum; 32 //cout << minn << endl; 33 } 34 } 35 cout << minn << endl; 36 } 37 return 0; 38 } View Code

還可以通過樹狀數(shù)組、線段樹、歸并排序求逆序數(shù)（這道題暴力就能過）

轉(zhuǎn)載于:https://www.cnblogs.com/ya-cpp/p/4104396.html

總結(jié)

以上是生活随笔為你收集整理的HD1394 Minimum Inversion Number的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。