首页 > ACM题库 > HDU-杭电 > HDU 1557 权利指数-枚举-[解题报告] C++
2013
12-12

HDU 1557 权利指数-枚举-[解题报告] C++

权利指数

问题描述 :

在选举问题中,总共有n个小团体,每个小团体拥有一定数量的选票数。如果其中m个小团体的票数和超过总票数的一半,则此组合为“获胜联盟”。n个团体可形成若干个获胜联盟。一个小团体要成为一个“关键加入者”的条件是:在其所在的获胜联盟中,如果缺少了这个小团体的加入,则此联盟不能成为获胜联盟。一个小团体的权利指数是指:一个小团体在所有获胜联盟中成为“关键加入者”的次数。请你计算每个小团体的权利指数。

输入:

输入数据的第一行为一个正整数T,表示有T组测试数据。每一组测试数据的第一行为一个正整数n(0<n<=20)。第二行有n个正整数,分别表示1到n号小团体的票数。

输出:

对每组测试数据,在同一个行按顺序输出1到n号小团体的权利指数。

样例输入:

2
1
10
7
5 7 4 8 6 7 5

样例输出:

1
16 22 16 24 20 22 16

数据小,水题,直接穷举每一种组合,然后相应判断处理即可。

/*
 * hdu1557/win.cpp
 * Created on: 2013-6-1
 * Author    : ben
 */
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;
const int MAXN = 22;
int data[MAXN], result[MAXN], total;
int indexs[MAXN];
double half;

void initindexs() {
    for(int i = 0; i < MAXN; i++) {
        indexs[i] = 1 << i;
    }
}

void work(int state, int n) {
    int to = 0;
    for(int i = 0; i < n; i++) {
        if(state & indexs[i]) {
            to += data[i];
        }
    }
    if(to <= half) {
        return ;
    }
    for(int i = 0; i < n; i++) {
        if((state & indexs[i]) && to - data[i] <= half) {
            result[i]++;
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif
    int T, n;
    initindexs();
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        memset(result, 0, sizeof(result));
        total = 0;
        for(int i = 0; i < n; i++) {
            scanf("%d", &data[i]);
            total += data[i];
        }
        half = total / 2.0;
        int max_state = 1 << n;
        for(int state = 0; state < max_state; state++) {
            work(state, n);
        }
        printf("%d", result[0]);
        for(int i = 1; i < n; i++) {
            printf(" %d", result[i]);
        }
        putchar('\n');
    }
    return 0;
}

 

解题报告转自:http://www.cnblogs.com/moonbay/archive/2013/06/01/3112579.html