描述
吉老师的面前出现了一座汉诺塔！但是这个汉诺塔好像坏了，盘子并不是按照从大到小的顺序排列的……吉老师非常不开心，立志要把这个汉诺塔修好！吉老师每分钟可以交换挨在一起的两个盘子，吉老师希望用的时间最短，吉老师不会啊，你能帮帮吉老师吗？
输入
第一行1个整数N。
第二行为N 个非负整数，按从下到上的顺序给出每个盘子的大小。
对于50%的数据，2<=N<=1000。
对于100%的数据，2<=N<=100000。输出一个整数，表示最少需要交换多少次相邻的盘子才能将盘子递减排列。同样大小的盘子应该排在一起。
样例输入
15 21 3 10 8 5
样例输出
7
提示
吉老师经过多次尝试，发现最优情况下的每次交换中，一定是将小盘子放到大盘子的上面，这样它们就从逆序变成了顺序，而且只有这一对盘子从逆序变成了顺序，所以总共逆序的盘子对数恰好减少一。而当没有逆序的盘子时，汉诺塔就修好啦。
题解
1 1 #include <iostream> 2 2 #include <string.h> 3 3 #include <algorithm> 4 4 #include <stack> 5 5 #include <string> 6 6 #include <math.h> 7 7 #include <queue> 8 8 #include <stdio.h> 9 9 #include <string.h> 1010 #include <vector> 1111 #include <fstream> 1212 #define maxn 100005 1313 #define inf 999999 1414 #define cha 127 1515 using namespace std; 1616 1717 int n; 1818 int plate[maxn], tmp[maxn]; 1919 long sum; 2020 2121 void mysort(int left,int right) { 2222 if (left >= right)return; 2323 int mid = (left + right) / 2; 2424 mysort(left, mid), mysort(mid + 1, right); 2525 int i = left, j = mid + 1, p = left; 2626 while (i <= mid && j <= right) { 2727 if (plate[i] >= plate[j]) 2828 tmp[p++] = plate[i++]; 2929 else { 3030 tmp[p++] = plate[j++]; 3131 sum += mid - i + 1; 3232 } 3333 } 3434 while (i <= mid) 3535 tmp[p++] = plate[i++]; 3636 while (j <= right) 3737 tmp[p++] = plate[j++]; 3838 for (int p = left; p <= right; p++) 3939 plate[p] = tmp[p]; 4040 } 4141 4242 void init() { 4343 scanf("%d", &n); 4444 for (int i = 1; i <= n; i++) 4545 scanf("%d", &plate[i]); 4646 mysort(1, n); 4747 printf("%ld\n", sum); 4848 } 4949 5050 int main() 5151 { 5252 init(); 5353 return 0; 5454 }
View Code
照搬了之前的作业求逆序对。提示说得很清楚，坑点在于答案超过了int范围