source
Description
在選舉問題中，總共有n個小團(tuán)體永乌，每個小團(tuán)體擁有一定數(shù)量的選票數(shù)。如果其中m個小團(tuán)體的票數(shù)和超過總票數(shù)的一半具伍，則此組合為“獲勝聯(lián)盟”翅雏。n個團(tuán)體可形成若干個獲勝聯(lián)盟。一個小團(tuán)體要成為一個“關(guān)鍵加入者”的條件是：在其所在的獲勝聯(lián)盟中人芽，如果缺少了這個小團(tuán)體的加入望几，則此聯(lián)盟不能成為獲勝聯(lián)盟。一個小團(tuán)體的權(quán)利指數(shù)是指：一個小團(tuán)體在所有獲勝聯(lián)盟中成為“關(guān)鍵加入者”的次數(shù)啼肩。請你計算每個小團(tuán)體的權(quán)利指數(shù)橄妆。
Input
輸入數(shù)據(jù)的第一行為一個正整數(shù)T衙伶，表示有T組測試數(shù)據(jù)。每一組測試數(shù)據(jù)的第一行為一個正整數(shù)n（0<n<=20）害碾。第二行有n個正整數(shù)矢劲，分別表示1到n號小團(tuán)體的票數(shù)。
Output
對每組測試數(shù)據(jù)慌随，在同一個行按順序輸出1到n號小團(tuán)體的權(quán)利指數(shù)芬沉。
Sample Input
2
1
10
7
5 7 4 8 6 7 5
Sample Output
1
16 22 16 24 20 22 16
#include<cstdio>
#include<algorithm>
#include"string.h"
using namespace std;
int *val,*degree,average;
void subset(int n,int s)
{
int sum=0,cnt=0;
for(int i=0;i<n;i++)
if(s&(1<<i)){
sum+=val[n-i-1];
}
if(sum>average)
{
for(int i=0;i<n;i++)
if(s&(1<<i)){
if(sum-val[n-1-i]<=average)
degree[n-1-i]++;
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
val=new int[n];
degree=new int[n];
memset(degree,0,n*sizeof(int));
average=0;
for(int i=0;i<n;i++)
{
scanf("%d",val+i);
average+=val[i];
}
average/=2;
for(int i=0;i<(1<<n);i++)
subset(n,i);
for(int i=0;i<n-1;i++)
printf("%d ",degree[i]);
printf("%d\n",degree[n-1]);
}
}
