DZY Loves Balls

Accepts: 659

Submissions: 1393

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 262144/262144 K (Java/Others)

问题描述

DZY喜欢玩球。他有nn个球，装进一个大盒子里。每个球上面都写着一个整数。有一天他打算从盒子中挑两个球出来。他先均匀随机地从盒子中挑出一个球，记为AA。他不把AA放回盒子，然后再从盒子中均匀随机地挑出一个球，记为BB。如果AA上的数字严格大于BB上的数字，那么他就会感到愉悦。现在告诉你每个球上的数字，请你求出他感到愉悦的概率是多少。

输入描述

第一行tt，表示有tt组数据。接下来tt组数据。每组数据中，第一行包含一个整数nn，第二行包含nn个用空格隔开的正整数a_iai，表示球上的数字。(1\le t\le 300, 2\le n \le 300,1\le a_i \le 3001≤t≤300,2≤n≤300,1≤ai≤300)

输出描述

对于每个数据，输出一个实数答案，保留6位小数。

输入样例

231 2 33100 100 100

输出样例

0.5000000.000000

思路：

对于每个数a[i]求满足条件的个数(即所有数中比a[i]小的个数),然后用它们的和除以总的可能数即可。

include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           using namespace std;typedef long long ll;#define LL(x) (x<<1)#define RR(x) (x<<1|1)const int MOD = 1e9 + 7;const int maxn = 305;int n;int s[maxn];int a[maxn];int lowbit(int x){ return x&(-x);}void add(int pos,int x){ while(pos <= 300) { s[pos] += x; pos += lowbit(pos); }}int sum(int x){ int cnt= 0 ; while(x) { cnt += s[x]; x -= lowbit(x); } return cnt;}int main(){ int T; scanf("%d",&T); while(T--) { scanf("%d",&n); memset(s,0,sizeof(s)); for(int i = 1;i <= n;i++) { scanf("%d",&a[i]); add(a[i],1); } int all = 0; int num = n*(n-1); for(int i = 1;i <= n;i++) { all += sum(a[i]-1); } printf("%.6f\n",all*1.0/num); } return 0;}