Australian Voting

Australian Voting

时间: 1ms        内存:64M

描述:

Australian ballots require that voters rank all the candidates in order of choice. Initially only the first choices are counted, and if one candidate receives more than 50% of the vote then that candidate is elected. However, if no candidate receives more than 50%, all candidates tied for the lowest number of votes are eliminated. Ballots ranking these candidates first are recounted in favor of their highest-ranked non-eliminated candidate. This process of eliminating the weakest candidates and counting their ballots in favor of the preferred non-eliminated candidate continues until one candidate receives more than 50% of the vote, or until all remaining candidates are tied.

输入:

The first line of each case is an integer n indicating the number of candidates. The next n lines consist of the names of the candidates in order, each up to 80 characters in length and containing any printable characters. Up to 1,000 lines follow, each containing the contents of a ballot. Each ballot contains the numbers from 1 to n in some order. The first number indicates the candidate of first choice; the second number indicates candidate of second choice, and so on.

输出:

The output of each test case consists of either a single line containing the name of the winner or several lines containing the names of all candidates who are tied. The output of each two consecutive cases are separated by a blank line

示例输入:

3
John Doe
Jane Smith
Jane Austen
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2

示例输出:

John Doe

提示:

参考答案(内存最优[768]):

#include <stdio.h>
int main()
{
	const int maxn=20+1;
	const int size=1000;
	const int len=80+1;
	int n,m,a[size][maxn],p[size],v[maxn],i,s,t;
	char c[maxn][len];
	scanf("%d",&n);
	gets(c[0]);
	for(i=1; i<=n; i++)
	{
		gets(c[i]);
		v[i]=0;
	}
	for(m=0; m<size; m++)
	{
		if(scanf("%d",&a[m][0])!=1) break;
		for(i=1; i<n; i++) 
			scanf("%d",&a[m][i]);
		v[a[m][0]]++;
		p[m]=0;
	}
	while(1)
	{
		for(i=1,s=0,t=m; i<=n; i++)
		{
			if(v[i]>=0)
			{
				if(v[i]<t) t=v[i];
				if(v[i]>s) s=v[i];
			}
			if(v[i]*2>m) break;
		}
		if(i<=n||s==t)
		{
			for(i=1; i<=n; i++) if(v[i]==s) 
				printf("%s\n",c[i]);
			break;
		}
		for(i=1; i<=n; i++) 
			if(v[i]==t) 
				v[i]=-1;
		for(i=0; i<m; i++)
			if(v[a[i][p[i]]]<0)
			{
			while(v[a[i][p[i]]]<0) p[i]++;
			v[a[i][p[i]]]++;
		}
	}
	return 0;
}

参考答案(时间最优[0]):

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 50;
#define INF 0x3fffffff
int vote[1050][N];
int out[N], cnt[N];
char name[N][100];
int num;
int main()
{
    int  n, i, j;
    char str[1000];
    while(~scanf("%d%*c",&n))
    {
        for(i = 1; i <= n; i++)
            gets(name[i]);
        num = 0;
        while(gets(str) != NULL)
        {
            if(!strcmp(str, "")) break;
            int len = strlen(str);
            int s = 0, k = 0;
            for(i = 0; i < len; i++)
            {
                if(str[i] >= '0' && str[i] <= '9')
                    s = s * 10 + str[i] - '0';
                else
                {
                    vote[num][k++] = s;
                    s = 0;
                }
            }
            vote[num][k++] = s;
            num++;
        }
        memset(out, 0, sizeof(out));
        int flag = 0, rest = n, total = 0;
        while(rest > 1)
        {
            total = 0;
            memset(cnt, 0, sizeof(cnt));
            for(i = 0; i < num; i++)
            {
                for(j = 0; j < n; j++)
                {
                    if(!out[vote[i][j]])
                    {
                        cnt[vote[i][j]]++;
                        total++;
                        break;
                    }
                }
            }
            for(i = 1; i <= n; i++)
                if(cnt[i] * 2 > total && !out[i])
                {
                    printf("%s\n",name[i]);
                    flag = 1;
                    break;
                }
            if(flag) break;
            int mmin = INF, mmax = 0;
            for(i = 1; i <= n; i++)
            {
                if(!out[i])
                {
                    mmin = min(mmin, cnt[i]);
                    mmax = max(mmax, cnt[i]);
                }
            }
            if(mmin == mmax)break;
            for(i = 1; i <= n; i++)
                if(cnt[i] == mmin)
                {
                    out[i] = 1;
                    rest--;
                }
        }
        if(!flag)
        {
            for(i = 1; i <= n; i++)
                if(!out[i])
                    printf("%s\n", name[i]);
        }
        printf("\n");
    }
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注