选举问题，速速戳进来

︶ㄣ痕迹の天涯

选举问题
题目详情:
在许多选举的问题上，并不是每个人都是一张票的，很多时候会由于每个人的权利不同导致每个人的话事权也不一样（可认为所拥有的票数）假设有选举人V1,V2...Vk,他们所拥有的票数分别为w1,w2...wk;并设优势联盟为所有选举人的一个子集且他们的总票数超过一半。而Vi拥有的权利指数为在有他的所有优势联盟中，他退出便能使优势联盟变为劣势联盟的次数。若Vi一个人的票数便已经超过一半，则称他为独裁者，我们认为这种选举是不公平的。现在，我们就是要看一个选举系统是否存在独裁，若不存在，求出每个选举人的权利指数。

输入：第一行为T,表示有T个案例！每个案例第一行为k，表示有k个选举人（1<k<=20）,第二行为k个数，表示每个选举人所拥有的票数。

输出：若存在独裁，则输出"It's unfair!",否则输出每个选举人的权利指数。







答题说明:
输入案例：

2

2

5 1

5

3 4 5 6 7

输出案例：

It's unfair!

4 4 4 8 8
求问题代码。，，，O(∩_∩)O谢谢

似水无痕

写了下，感觉算法不是很好，你可以修改下

#include <stdio.h>
#include <stdlib.h>

int election(int start, int end, int *ballot, int *sum);
int comparator(const void *, const void *);
//void qsort ( void * base, size_t num, size_t size, int ( * comparator ) ( const void *, const void * ) );

int main()
{
        int ballot[20];
        int sum[1024 * 1024];
        
        int index;
        int t, k, i, j, p;
        int allsum;
        int rangeless, rangeabove;
        int temp, num1, num2, pow;
        double halfsum;
                
        scanf("%d", &t);
        
        for(i = 0; i < t; i++) {
                scanf("%d", &k);
                for(j = 0, allsum = 0; j < k; j++) {
                        scanf("%d", ballot + j);
                        allsum += ballot[j];
                }
                halfsum = allsum / 2.0;
                //判断是否有独裁
                for(j = 0; j < k; j++) {
                        if(ballot[j] > halfsum) break;
                }
                if(j != k) {
                        printf("It's unfair!\n");
                        continue;
                }
                //计算权数
                for(j = 0; j < k; j++) {
                        rangeless = halfsum - ballot[j] + 1;
                        rangeabove = (halfsum - (int)halfsum)*2 + (int)halfsum - 1;
                        temp = ballot[j];
                        ballot[j] = ballot[k - 1];
                        
                        index = election(0, k-2, ballot, sum);
                        qsort(sum, index, sizeof(int), comparator);
                        //printf("\n%d %d\n", rangeless, rangeabove);
                        /*for(p = 0; p < index; p++) {
                                printf("%d ", sum[p]);
                        }*/
                        
                        num1 = binfind(sum, index, rangeless);
                        //printf("\n%d\n", num1);
                        if(sum[num1] < rangeless) {
                                while(sum[num1++] < rangeless && num1 < index);
                                num1--;
                        } else {
                                while(sum[num1--] >= rangeless && num1 >= 0);
                                num1 = (num1 == -1) ? 0 : num1+2;
                        }
                        
                        num2 = binfind(sum, index, rangeabove);
                        if(sum[num2] <= rangeabove) {
                                while(sum[num2++] <= rangeabove && num1 < index);
                                num2 = (num2 == index) ? num2-1 : num2-2;
                        } else {
                                while(sum[num2--] > rangeabove && num2 >=0);
                                num2++;
                        }
                        //printf("\n%d %d\n", num2, num1);
                        printf("%d ", num2 - num1 +1);
                        
                        ballot[j] = temp;
                        
                }
                printf("\n");
        }
        
        return 0;
        
}

int election(int start, int end, int *ballot, int *sum)
{
        int index; // 下一个要写的数的位置
        if(start == end) {
                sum[0] = 0;
                sum[1] = ballot[end];
                index = 2;
                return index;
        }
        
        //start++;
        index = election(start+1, end, ballot, sum);
        
        int i;
        for(i = 0; i < index; i++) {
                sum[index + i] = sum[i] + ballot[start];
        }
        return index * 2;

}

int comparator(const void *a, const void *b) 
{
        if(*(int *)a < *(int *)b)
                return -1;
        else if(*(int *)a == *(int *)b)
                return 0;
        else
                return 1;
                        
}

int binfind(int val[] , int num , int value)
{
        int start = 0;
        int end = num - 1;
        int mid = (start + end)/2;
        while(val[mid] != value && start < end) {
                if (val[mid] > value) {
                        end = mid - 1;
                } else if (val[mid] < value) {
                        start = mid + 1;
                }
                mid = ( start + end )/2; 
        }
        return mid;
}

︶ㄣ痕迹の天涯

似水无痕 发表于 2014-4-7 18:04

                               
登录/注册后可看大图

写了下，感觉算法不是很好，你可以修改下

回复晚了，抱歉啊，你这个方法确实可以，不过代码太长了，运行的话直接属于超时，不过还是谢谢了，不知道能更简洁点不

似水无痕

你是在做acm，自己暂时还没想到什么更有效的算法:cry

似水无痕

新鱼友一个，不能添加好友:cry

︶ㄣ痕迹の天涯

似水无痕 发表于 2014-4-10 22:48

                               
登录/注册后可看大图

新鱼友一个，不能添加好友

没事，能写出这个问题的程序，咱都一样啦

youngk

楼主  可以把你的代码过来看看吗？？？？我写的没过