3715. 最少交换次数（北京师范大学考研机试题）

思路：暴力求逆序对，记录每个位置的逆序对数

代码：

#include 
#include 
#include 

using namespace std;

const int N = 1010;
int w[N], ans[N];

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> w[i];
    
    for(int i = 0; i < n; i ++) {
        for (int j = 0; j < i; j ++) 
            if(w[j] > w[i])
                ans[w[i]] ++;
        
    }
    
    int sum = 0;
    for(int i = 1; i <= n; i ++) {
           
        cout << ans[i] << ' ';
        sum += ans[i];
    }
    cout << endl;
    cout << sum << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32