选举问题，速速戳进来
选举问题题目详情:
在许多选举的问题上，并不是每个人都是一张票的，很多时候会由于每个人的权利不同导致每个人的话事权也不一样（可认为所拥有的票数）假设有选举人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谢谢
本帖最后由 似水无痕 于 2014-4-7 18:05 编辑
写了下，感觉算法不是很好，你可以修改下#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;
int sum;
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;
}
halfsum = allsum / 2.0;
//判断是否有独裁
for(j = 0; j < k; j++) {
if(ballot > halfsum) break;
}
if(j != k) {
printf("It's unfair!\n");
continue;
}
//计算权数
for(j = 0; j < k; j++) {
rangeless = halfsum - ballot + 1;
rangeabove = (halfsum - (int)halfsum)*2 + (int)halfsum - 1;
temp = ballot;
ballot = ballot;
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);
}*/
num1 = binfind(sum, index, rangeless);
//printf("\n%d\n", num1);
if(sum < rangeless) {
while(sum < rangeless && num1 < index);
num1--;
} else {
while(sum >= rangeless && num1 >= 0);
num1 = (num1 == -1) ? 0 : num1+2;
}
num2 = binfind(sum, index, rangeabove);
if(sum <= rangeabove) {
while(sum <= rangeabove && num1 < index);
num2 = (num2 == index) ? num2-1 : num2-2;
} else {
while(sum > rangeabove && num2 >=0);
num2++;
}
//printf("\n%d %d\n", num2, num1);
printf("%d ", num2 - num1 +1);
ballot = temp;
}
printf("\n");
}
return 0;
}
int election(int start, int end, int *ballot, int *sum)
{
int index; // 下一个要写的数的位置
if(start == end) {
sum = 0;
sum = ballot;
index = 2;
return index;
}
//start++;
index = election(start+1, end, ballot, sum);
int i;
for(i = 0; i < index; i++) {
sum = sum + ballot;
}
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 != value && start < end) {
if (val > value) {
end = mid - 1;
} else if (val < value) {
start = mid + 1;
}
mid = ( start + end )/2;
}
return mid;
}
似水无痕 发表于 2014-4-7 18:04 static/image/common/back.gif
写了下，感觉算法不是很好，你可以修改下
回复晚了，抱歉啊，你这个方法确实可以，不过代码太长了，运行的话直接属于超时，不过还是谢谢了，不知道能更简洁点不 你是在做acm，自己暂时还没想到什么更有效的算法:cry 新鱼友一个，不能添加好友:cry 似水无痕 发表于 2014-4-10 22:48 static/image/common/back.gif
新鱼友一个，不能添加好友
没事，能写出这个问题的程序，咱都一样啦 楼主可以把你的代码过来看看吗？？？？我写的没过
页:
[1]