首页 / 软件开发 / 数据结构与算法 / UVa 12004 Bubble Sort:想法题

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&page=show_problem&problem=3155

枚举交换次数算期望太麻烦，不妨换个思路：对于任意一对数字，它们之间发生交换的概率和不交换的概率是相等的，那这对数字提供的期望值就为1/2。总共有C（n,2）对数字，所以最终的期望值就为n*（n-1）/4

完整代码：

01./*0.015s*/02.03.#include<cstdio>04.05.int main（）06.{07.long long x;08.int T, cas = 0;09.scanf（"%d", &T）;10.while （T--）11.{12.scanf（"%lld", &x）;13.x = x * （x - 1） >> 1;14.printf（"Case %d: ", ++cas）;15.if （x & 1） printf（"%lld/2
", x）;16.else printf（"%lld
", x >> 1）;17.}18.}