首页 > 试题广场 >

Spring Outing

[编程题]Spring Outing
  • 热度指数：3398 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
You class are planning for a spring outing. N people are voting for a destination out of K candidate places.
The voting progress is below:
First the class vote for the first candidate place. If more than half of the class agreed on the place, the place is selected. The voting ends.
Otherwise they vote for the second candidate place. If more than half of the class agreed on the place, the place is selected. The voting ends.
Otherwise they vote for the third candidate place in the same way and go on.
If no place is selected at last there will be no spring outing and everybody stays at home.
Before the voting, the Chief Entertainment Officer did a survey, found out every one's preference which can be represented as a permutation of 0, 1, ... K. (0 is for staying at home.) For example, when K=3, preference "1, 0, 2, 3" means that the first place is his first choice, staying at home is the second choice, the second place is the third choice and the third place is the last choice.
The Chief Entertainment Officer sends the survey results to the class. So everybody knows the others' preferences. Everybody wants his more prefered place to be selected. And they are very smart, they always choose the optimal strategy in the voting progress to achieve his goal.
Can you predict which place will be selected?

输入描述:
The first line contains two integers, N and K, the number of people in your class and the number of candidate places.
The next N lines each contain a permutation of 0~K, representing someone's preference.
For 40% of the data, 1 <= N, K <= 10
For 100% of the data, 1 <= N, K <= 1000


输出描述:
Output the selected place. Or "otaku" without quotes if no place is selected.

In the sample case, if the second peoson vote against the first place, no place would be selected finally because the first person must vote against the second place for his own interest. Considering staying at home is a worse choice than the first place, the second person's optimal strategy is voting for the first place. So the first place will be selected
示例1

输入

2 2
1 0 2
2 1 0

输出

1
算法知识视频讲解
添加回答
Java
ifnotadream?头像 ifnotadream? 
import java.util.*;
public class Main{
    public static void main(String[] args){
        new Main().process();
    }
    
    private int N;
    
    private int K;
    
    private void process(){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNextInt()){
            N=sc.nextInt();//N represents number of persons
            K=sc.nextInt();//K represents number of destinaitons
            pArray=new int[N][];
            for(int i=0;i<N;i++){
                pArray[i]=new int[K+1];
                for(int j=0;j<K+1;j++){
                    pArray[i][j]=sc.nextInt();
                }
            }
            voteRecords=new int[K+2];
            for(int i=0;i<=K;i++){voteRecords[i]=-1;}//Initiate recoards
            int dest=vote(1);//Get result
            String result=null;
            if(dest==0) result="otaku";
            else result=dest+"";
            voteRecords=null;//Release memory
            System.out.println(result);
        }
        sc.close();
    }
    
    private int[] voteRecords;
    
    private int vote(int dest){
        if(dest==K+1){
            voteRecords[dest]=0; 
            return 0;//Stay at home
        }
        if(voteRecords[dest+1]==-1){
            vote(dest+1);
        }
        voteRecords[dest]=voteIn(dest,voteRecords[dest+1]);
        return voteRecords[dest];
    }
    
    private int[][] pArray;
    
    private int voteIn(int dest1,int dest2){
        int counter=0;
        for(int i=0;i<N;i++){
            int p1=0,p2=0;
            for(int j=0;j<K+1;j++){
                if(pArray[i][j]==dest1){p1=j;continue;}
                if(pArray[i][j]==dest2){p2=j;continue;}
            }
            if(p1<p2) counter++;
        }
        if(counter>N/2) return dest1;
        else return dest2;
    }
}
本题采用递归：
vote(int k)函数的含义：前k-1次投票结果都是反对的情况下，产生的最终投票结果
题目条件：N个人投票，K个可选目的地
递归过程：
(1) 如果前K次投票结果都是反对，那么呆在家里。
即,
k=K+1时vote(K+1)=0;
(2) 如果前k次投票结果都是反对，那么最终结果取决于第k次以后的投票结果。
即，
vote(k)=vote(k+1)         ，半数以上的人反对去k
vote(k)=k                     , 半数以上的人同意去k 

2 2
1 0 2
2 1 0
以题目给的输入为例
vote(3)=0，
    因为前两次投票的结果都是反对
vote(2)=0，
    目的地1的投票结果已经是反对，如果此次投票结果为反对，那么vote(2)=vote(3)=0；否则vote(2)=2
    对于第一个人来说，他更希望呆在家里，所以他会投反对票，这样就有超过一半的人反对了，因此vote(2)=vote(3)=0
vote(1)=1
    如果第一次投票的结果是反对，那么vote(1)=vote(2)=0
    否则vote(1)=1
    与呆在家里相比，两个人都更希望去1，所以两个人都赞成
最终结果为vote(1)=1
发表于 2016-10-06 17:58:07 回复(0)
Java
Holiday_12138头像 Holiday_12138 
 import java.util.*;

public class Main{
	static int[][] p;
    public static boolean judge(int row,int k,int pi,int pj){
        for(int i=0;i<k+1;i++){
            if(p[row][i]==pi)
                return true;
            if(p[row][i]==pj)
                return false;
        }
        return true;
    }
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
        int n,k;
        while(sc.hasNext()){
            n=sc.nextInt();
            k=sc.nextInt();
            p=new int[n][k+1];
            for(int i=0;i<n;i++)
                for(int j=0;j<k+1;j++)
                	p[i][j]=sc.nextInt();
            
            int pk=0;
            int vote;
            for(int i=k;i>0;i--){
                vote=0;
                for(int j=0;j<n;j++){
                    if(p[j][0]==i)
                        vote++;
                    else if(judge(j,k,i,0)){
                        if(judge(j,k,i,pk)){
                            vote++;
                        }
                    }
                }
                if(vote>n/2)
                    pk=i;
            }
            if(pk==0)
                System.out.println("otaku");
            else
                System.out.println(pk);
        }
      
       sc.close();
	}
}


/*您的代码已保存
答案错误:您提交的程序没有通过所有的测试用例
case通过率为5.88%

测试用例:
10 6
5 6 4 3 1 0 2
6 3 2 0 5 4 1
4 1 2 0 6 3 5
1 2 5 6 0 3 4
3 5 1 0 4 6 2
2 4 6 5 0 3 1
4 1 5 6 3 0 2
2 6 0 4 3 1 5
2 5 4 0 3 6 1
0 3 1 2 4 5 6

对应输出应该为:

1

你的输出为:

6讲道理，第2 6  8 9 10号 选家里蹲也不会选地点1啊？1能胜出？
*/

编辑于 2016-09-20 19:56:59 回复(2)
提交观点

问题信息

贪心
难度：
2条回答 8994浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号