选举问题，速速戳进来

︶ㄣ痕迹の天涯

选举问题
题目详情:
在许多选举的问题上，并不是每个人都是一张票的，很多时候会由于每个人的权利不同导致每个人的话事权也不一样（可认为所拥有的票数）假设有选举人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谢谢

似水无痕

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

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. int election(int start, int end, int *ballot, int *sum);
   
5. int comparator(const void *, const void *);
   
6. //void qsort ( void * base, size_t num, size_t size, int ( * comparator ) ( const void *, const void * ) );
   
7. 
   
8. int main()
   
9. {
   
10.         int ballot[20];
    
11.         int sum[1024 * 1024];
    
12.         
    
13.         int index;
    
14.         int t, k, i, j, p;
    
15.         int allsum;
    
16.         int rangeless, rangeabove;
    
17.         int temp, num1, num2, pow;
    
18.         double halfsum;
    
19.                
    
20.         scanf("%d", &t);
    
21.         
    
22.         for(i = 0; i < t; i++) {
    
23.                 scanf("%d", &k);
    
24.                 for(j = 0, allsum = 0; j < k; j++) {
    
25.                         scanf("%d", ballot + j);
    
26.                         allsum += ballot[j];
    
27.                 }
    
28.                 halfsum = allsum / 2.0;
    
29.                 //判断是否有独裁
    
30.                 for(j = 0; j < k; j++) {
    
31.                         if(ballot[j] > halfsum) break;
    
32.                 }
    
33.                 if(j != k) {
    
34.                         printf("It's unfair!\n");
    
35.                         continue;
    
36.                 }
    
37.                 //计算权数
    
38.                 for(j = 0; j < k; j++) {
    
39.                         rangeless = halfsum - ballot[j] + 1;
    
40.                         rangeabove = (halfsum - (int)halfsum)*2 + (int)halfsum - 1;
    
41.                         temp = ballot[j];
    
42.                         ballot[j] = ballot[k - 1];
    
43.                         
    
44.                         index = election(0, k-2, ballot, sum);
    
45.                         qsort(sum, index, sizeof(int), comparator);
    
46.                         //printf("\n%d %d\n", rangeless, rangeabove);
    
47.                         /*for(p = 0; p < index; p++) {
    
48.                                 printf("%d ", sum[p]);
    
49.                         }*/
    
50.                         
    
51.                         num1 = binfind(sum, index, rangeless);
    
52.                         //printf("\n%d\n", num1);
    
53.                         if(sum[num1] < rangeless) {
    
54.                                 while(sum[num1++] < rangeless && num1 < index);
    
55.                                 num1--;
    
56.                         } else {
    
57.                                 while(sum[num1--] >= rangeless && num1 >= 0);
    
58.                                 num1 = (num1 == -1) ? 0 : num1+2;
    
59.                         }
    
60.                         
    
61.                         num2 = binfind(sum, index, rangeabove);
    
62.                         if(sum[num2] <= rangeabove) {
    
63.                                 while(sum[num2++] <= rangeabove && num1 < index);
    
64.                                 num2 = (num2 == index) ? num2-1 : num2-2;
    
65.                         } else {
    
66.                                 while(sum[num2--] > rangeabove && num2 >=0);
    
67.                                 num2++;
    
68.                         }
    
69.                         //printf("\n%d %d\n", num2, num1);
    
70.                         printf("%d ", num2 - num1 +1);
    
71.                         
    
72.                         ballot[j] = temp;
    
73.                         
    
74.                 }
    
75.                 printf("\n");
    
76.         }
    
77.         
    
78.         return 0;
    
79.         
    
80. }
    
81. 
    
82. int election(int start, int end, int *ballot, int *sum)
    
83. {
    
84.         int index; // 下一个要写的数的位置
    
85.         if(start == end) {
    
86.                 sum[0] = 0;
    
87.                 sum[1] = ballot[end];
    
88.                 index = 2;
    
89.                 return index;
    
90.         }
    
91.         
    
92.         //start++;
    
93.         index = election(start+1, end, ballot, sum);
    
94.         
    
95.         int i;
    
96.         for(i = 0; i < index; i++) {
    
97.                 sum[index + i] = sum[i] + ballot[start];
    
98.         }
    
99.         return index * 2;
    
100. 
     
101. }
     
102. 
     
103. int comparator(const void *a, const void *b)
     
104. {
     
105.         if(*(int *)a < *(int *)b)
     
106.                 return -1;
     
107.         else if(*(int *)a == *(int *)b)
     
108.                 return 0;
     
109.         else
     
110.                 return 1;
     
111.                         
     
112. }
     
113. 
     
114. int binfind(int val[] , int num , int value)
     
115. {
     
116.         int start = 0;
     
117.         int end = num - 1;
     
118.         int mid = (start + end)/2;
     
119.         while(val[mid] != value && start < end) {
     
120.                 if (val[mid] > value) {
     
121.                         end = mid - 1;
     
122.                 } else if (val[mid] < value) {
     
123.                         start = mid + 1;
     
124.                 }
     
125.                 mid = ( start + end )/2;
     
126.         }
     
127.         return mid;
     
128. }

复制代码

︶ㄣ痕迹の天涯

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

                               
登录/注册后可看大图

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

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

似水无痕

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

似水无痕

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

︶ㄣ痕迹の天涯

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

                               
登录/注册后可看大图

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

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

youngk

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