source
Description
在选举问题中，总共有n个小团体，每个小团体拥有一定数量的选票数。如果其中m个小团体的票数和超过总票数的一半，则此组合为“获胜联盟”。n个团体可形成若干个获胜联盟。一个小团体要成为一个“关键加入者”的条件是：在其所在的获胜联盟中，如果缺少了这个小团体的加入，则此联盟不能成为获胜联盟。一个小团体的权利指数是指：一个小团体在所有获胜联盟中成为“关键加入者”的次数。请你计算每个小团体的权利指数。
Input
输入数据的第一行为一个正整数T，表示有T组测试数据。每一组测试数据的第一行为一个正整数n（0<n<=20）。第二行有n个正整数，分别表示1到n号小团体的票数。
Output
对每组测试数据，在同一个行按顺序输出1到n号小团体的权利指数。
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]);
}
}
