湫湫系列故事——植樹節

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? Time Limit: 1000/500 MS (Java/Others)????Memory Limit: 65535/32768 K (Java/Others)

Problem Description 今天是一年一度的植樹節，騰訊幼兒園要求每個老師在班里選出幾個小朋友一起去野外種植小樹苗，根據學校的整體安排，湫湫老師的班里要選出3個小朋友。??已知湫湫的班里共有n個孩子，每個孩子有Bi個朋友(i從1到n)，且朋友關系是相互的，如果a小朋友和b小朋友是朋友，那么b小朋友和a小朋友也一定是好朋友。為了選擇的公平性，湫湫老師會隨機抽取3個小朋友出來(每個人被抽到的概率相同)，但是她很希望這3個小朋友之間的關系完全相同，湫湫老師想請你幫她算算抽到的3個小朋友正好關系相同的概率是多少？
　　PS. 關系相同就是指要么3個人互相是好朋友，要么3個人互相都不是好朋友。
Input 輸入數據第一行是一個整數T(1<=T<=1000)，表示輸入數據的組數；每組數據的第一行是一正整數n表示孩子的總數(2<n<=1000)，第二行有n個數Bi (i從1到n)，分別代表每個小朋友的朋友的個數。
Output 對于每組數據，請輸出抽到的3個小朋友關系相同的概率，結果保留3位小數。
Sample Input 1 5 3 3 3 3 4
Sample Output 0.400 這個問題直接求不太好求，所以我們可以求它的反面，即求3人關系不一樣的情況，然后用總數減去不一樣的就是一樣的。不一樣的情況就是：有兩個人是朋友，但和第三個人不是朋友，所以對于第i個人，可以從他的朋友中選出一個，再從不是他的朋友中選出一個，然后加上他自己，最后求和除以2就是不一樣的數量（因為每個人都算了2次）。 #include<stdio.h> int main() {int a, t, n, i;scanf("%d",&t);while(t--){scanf("%d",&n);int num = 0;for(i = 0; i < n; i++){scanf("%d",&a);num += a * (n - 1 - a);}num /= 2;int sum = n * (n-1) * (n-2) / 6;printf("%.3lf\n",(sum - num)*1.0 / sum);}return 0; }

總結

以上是生活随笔為你收集整理的hdu 4503 湫湫系列故事——植树节的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。