题解 UVA12004 【Bubble Sort】
死神审判
·
·
题解
简单题意：
求出对 n 个数进行冒泡排序的交换次数。
思路&解析：
经过分析，其实就是让你求出 数字对的个数 \times\frac{1}2。数字对的个数就是 C^2_n，然后\times\frac{1}2 就可以了。
虽然公式得到了，但是需要整理一下（毕竟计算机不会直接输出 C^2_n）。
C^2_n\times\frac{1}2=\frac{C^2_n}2=\frac{n*(n-1)}4
最后注意，如果$\frac{n*(n-1)}2$已经是奇数，也就是说不能被最后的一个 $2$ 整除了，要用分数表示，例如 $1/2$。
### 代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
int k;
cin>>k;
k=k*(k-1)/2;
if(k%2==0)cout<<"Case "<<i<<": "<<k/2<<"\n";
else cout<<"Case "<<i<<": "<<k<<"/2\n";//套公式
}
return 0;
}
```
### 最后的提醒：
UVA现在好卡，如果卡了几次后就不要一直交了，~~浪费提交次数~~。