HDOJ 5645-DZY Loves Balls【模拟】

刺骨的言语ヽ痛彻心扉 2022-07-29 09:16 1阅读 0赞

# DZY Loves Balls #

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)

Total Submission(s): 20 Accepted Submission(s): 18

Problem Description

DZY loves playing balls.  
  
He has  n![Image 1][] balls in a big box. On each ball there is an integer written.  
  
One day he decides to pick two balls from the box. First he randomly picks a ball from the box, and names it  A![Image 1][]. Next, without putting  A![Image 1][] back into the box, he randomly picks another ball from the box, and names it  B![Image 1][].  
  
If the number written on  A![Image 1][] is strictly greater than the number on  B![Image 1][], he will feel happy.  
  
Now you are given the numbers on each ball. Please calculate the probability that he feels happy.

Input

First line contains  t![Image 1][] denoting the number of testcases.  
  
 t![Image 1][] testcases follow. In each testcase, first line contains  n![Image 1][], second line contains  n![Image 1][] space-separated positive integers  a![Image 1][]i![Image 1][]![Image 1][], denoting the numbers on the balls.  
  
(  1≤t≤300,2≤n≤300,1≤a![Image 1][]i![Image 1][]≤300![Image 1][])

Output

For each testcase, output a real number with 6 decimal places.

Sample Input

2
    3
    1 2 3
    3
    100 100 100

Sample Output

0.500000
    0.000000

解题思路：

有n个球，我们先拿出一个再拿出一个，问先拿出的比后拿出的大的概率。

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int map[100000];
    int num[1000];
    int C(int n,int x)  
    {  
        int temp=1;    
        for(int i=1;i<=x;i++)    
            temp=temp*(n-i+1)/i;     
        return temp;    
    }  
    int main()
    {
    	int t;
    	scanf("%d",&t);	
    	while(t--)
    	{
    		memset(num,0,sizeof(num));
    		int a;
    		scanf("%d",&a);
    		int yy=a;
    		int i,j;
    		for(i=0;i<a;i++)
    		{
    			scanf("%d",&map[i]);
    			num[map[i]]++;
    		}
    		int xx=a*(a-1);
    	//	printf("%d\n",xx);
    		int wc=0;
    		for(i=1;i<=300;i++)
    		{
    			if(num[i]!=0)
    			{
    				wc+=(yy-num[i])*num[i];
    				yy-=num[i];
    			}
    		}
    	//	printf("%d\n",wc);
    		double gai;
    		gai=(double)wc/xx;
    		printf("%lf\n",gai);
    	}
    	return 0;
    }

[Image 1]: