重庆公司招聘_百度搜索排名优化_中国十大策划公司排名_如何做网站营销

Problem - 1214 (hdu.edu.cn)

---

解题思路：

        结果的顺序就是原序列的逆序，例如12345就是54321为结果顺序。同时将一个顺序序列（非环）变成逆序需要的次数为。想要的得到最短的交换次数，只需要将环尽量对半分，然后分别对两部分进行顺序序列变逆序次数的计算，再将两部分次数相加即可。（ps:只有尽量对半分，才能使得逆序所需次数最少，3:7之类都是不行的）

---

AC代码：

#include<bits/stdc++.h>
using namespace std;int slove(int n){return n * (n - 1) / 2;
}
int main()
{int n;while(cin >> n){  // 题目没有输入样例次数cout << slove(n/2) + slove(n - n / 2) << '\n';}return 0;} 

---

知识点：

        思维题，数学