australian voting.cpp

programming changllening p51页australian voting 解答源码

#include<iostream>
#include<string>
#define isOut(i) cal[i]==-1 
using namespace std;
int main()
{
    int ncase;
    cin>>ncase;
   // for(int i=0;i<ncase;i++)
    //{
            int candidate=20;
            cin>>candidate;
            string* names=new string [candidate+1];//从一开始 
            int* cal=new int [candidate+1];//从一开始 
            int* nowVote=new int [candidate+1];//记录n号参选者的最近的一个支持者 用来link 
            for(int p=0;p<=candidate;p++)
            {cal[p]=0;nowVote[p]=-9999;}
			 //initialize
            cin.ignore();//忽略第一个换行符 
            for(int j=1;j<=candidate;j++)
                getline(cin,names[j]);         
			int vote[1001][10];//志愿顺序从零开始0志愿1志愿;票从0开始到man-1张
			char* tempvote=new char[80];
            int man=0;    
			
            cin.getline(tempvote,30);
            while(strlen(tempvote)>=2)//&&isLegal(a,b,c)
			{  
				 vote[man][0]=atoi(strtok(tempvote," \n"));
                 for(int q=1;q<candidate;q++)
				{
				  vote[man][q]=atoi(strtok(NULL," \n"));
				 }
                 man++;
				 cin.getline(tempvote,30);
                  //这种处理默认系统的输入不会缺失不会输入无效值
            }

			//以上为IO处理
			int* now=new int[man];
            int* link=new int[man];
			for(int a=0;a<man;a++)//扫描第一遍
			{   int v=vote[a][0];
				cal[v]++;
				now[a]=0;//因为是第一遍;
			//	if(nowVote[v]=-9999)
		//			link[a]=0-v;
		//		else link[a]=nowVote[v];//将前一位投票人link起来
		//		nowVote[v]=a;	
			}
			bool flag=false;
			int min=10000;
            for(int c1=1;c1<=candidate;c1++)
			{	if(cal[c1]<min)
			    min=cal[c1];
				if((cal[c1]*1.0/man)>0.5)
				{
					cout<<names[c1];//获胜则跳出
					flag=true;//有人胜出
					break;
				}
			}
            for(int c2=1;c2<=candidate;c2++)
	        	if(cal[c2]==min)
			    cal[c2]=-1;
            bool token=false;//记录是否是淘汰人
            while(flag!=true)
			{   for(int c3=0;c3<man;c3++)
			{
				while(cal[vote[c3][now[c3]]]==-1)//已被淘汰暂时没有用到link
				{	    now[c3]++;
				        token=true;
				}
				if(token){cal[vote[c3][now[c3]]]++;token=false;}
			
			}
				    min=10000;
	   		    for(int c1=1;c1<=candidate;c1++)
					{	if(cal[c1]<min)
					    min=cal[c1];
						if((cal[c1]*1.0/man)>0.5)
						{
						cout<<names[c1];//获胜则跳出
						flag=true;//有人胜出
						break;
						}
					}
                for(int c2=1;c2<=candidate;c2++)
	        	    if(cal[c2]==min)
			          cal[c2]=-1;
			}



            
    //}

   // cout<<link[1];
   // cout<<nowVote[1];
   // cout<<cal[2];
   // system("PAUSE");
	return 0;
}