Spring Outing

对于每一个地点，我们可以把人分成三类：

1、当前地点在这类人的眼里优先级是最高的；

2、当前地点在这类人的眼里优先级不是最高，但是比蹲在家里好；

3、宁愿蹲家里也不去当前地点的人；

那么当给某个地点投票时，1、3类人的意愿是很明确的，优先级最高的肯定投同意，家里蹲的肯定投反对，剩下的2类人就是要考虑投与不投的，而这类人考虑的因素就是后面能否确定得到【而不是存在】更好的选择。并且我们还知道，如果某个地点的优先级比0还低的话那么这个地点也是肯定被投反对的。

2、因此我们知道了对p2的投票结果，回到p1，如果2投X票的话，那么会造成家里蹲的结果。

例如上面的选择过程，对p1进行投票时，我们知道过了p1下一个pk点是home，而对学生s2来说，p1的优先级是高于home的，并且没有其它优先级高于p1的可达点（当然，有的话home就不是pk点了）

 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能胜出？
*/

好彩我啊，题目虽然看懂了，就是没思路，5555
看了大神的答案之后，加上自己的理解，和自己爬过的坑

package com.special.first;

import java.util.Scanner;

/**
 * 微软03-Spring Out
 *
 * 技巧一：我们的二维数组用哈希的思想，地点作为索引，而值作为优先级
 *
 * 算法的第一次理解，先假设一个地点为预选，然后每次对新地点投票时都会与上一个局部优解比较，取局部最优
 * 刚开始我想了想这个算法，这样是不对的，0其实与其他地点是无区别，
 * 这样的结果会严重依赖初始的地点为0
 *
 * 后来我又看了看题，这个题其实是默认了一个条件就是，一个人对于低于家里蹲的所有的地点都会投反对
 * 这个题带了点生活上的意思，就是我想出去玩，只要比家里蹲好就行。
 * 但是我不想出去玩，敲代码很累啊，还不休息休息，Mdzz, 你们提出的地点我肯定反对
 *
 * 还有一点就是之所以我们倒着来，是因为假设前k - 1前都不通过，那么再对K投票时，大家只会考虑k和家里蹲的权衡了
 * 然后我们再对k - 1投票时，就可以依据k的结果，来对比选择，这样每次都只需比较一个地点就行，而这个地点恰巧是
 * 之后的地点的局部最优。这样的做的原因是有些人对于当前地点不是最优或者比家里蹲好时，他会想之后可不可能存在
 * 比当前地点更好的选择呢。我们从后投票倒推就是要告诉这些人不要脑补了，我们帮你计算了如果你否定当前节点，你之后会得到
 * 什么地点，这时在面对当前节点，他们就只权衡当前节点和之后的最优比较就行了。
 * 这思想，很好，赞一个。
 * Create by Special on 2018/2/14 17:25
 */
public class Pro006 {

    public static int getPlace(int[][] votes, int n, int k){
        int selected = 0, count = 0;
        for(int i = k; i > 0; i--){
            count = 0;
            for(int j = 0; j < n; j++){
                if(votes[j][i] < votes[j][selected]){
                    count++;
                }
            }
            if(count > n / 2){
                selected = i;
            }
        }
        return selected;
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while(input.hasNext()){
            int n = input.nextInt();
            int k = input.nextInt(), place;
            int[][] votes = new int[n][k + 1];
            for(int i = 0; i < n; i++){
                for(int j = 0; j <= k; j++){
                    place = input.nextInt();
                    votes[i][place] = j;
                }
            }
            int selected = getPlace(votes, n, k);
            System.out.println(selected == 0 ? "otaku" : selected);
        }
    }
}

 #include <iostream>

using namespace std;

const int MAX = 1010;
int n,k,level;

void Fun(int a[MAX][MAX], int m)
{
    int vote=0;
    for(int i=0;i<n;i++)
    {
        if(a[i][m] < a[i][level])
            vote++;
    }
    if(vote > n/2)
        level = m;
}

int main()
{
    while(cin>>n>>k)
    {
        int a[MAX][MAX],t;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<k+1;j++)
            {
                cin>>t;
                a[i][t] = j;
            }
     
        }
        level = 0;
        for(int i=k;i>0;i--)
            Fun(a,i);
        if(level == 0)
            cout<<"otaku"<<endl;
        else
            cout<<level<<endl;
    }
    return 0;
} 

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        while (s.hasNext()) {
            print(s);
        }
    }

    private static void print(Scanner s) {
        int n = s.nextInt(), k = s.nextInt();
        int A[][] = new int[n + 1][k + 2], B[] = new int[k + 2];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k + 1; j++) {
                A[i][j] = s.nextInt();
            }
        }

        for (int i = k; i >= 1; i--) {
            int c = 0;
            for (int x = 1, p1 = 0, p2 = 0; x <= n; x++) {
                for (int y = 1; y <= k + 1; y++) {
                    if (A[x][y] == i)
                        p1 = y;
                    if (A[x][y] == B[i + 1])
                        p2 = y;
                }
                if (p1 < p2)
                    c++;
            }
            if (c > n / 2)
                B[i] = i;
            else
                B[i] = B[i + 1];
        }
        System.out.println(B[1] == 0 ? "otaku" : B[1]);
    }
}

/*题目应该逆向考虑，因为每个人要达到自己的最优解，即尽可能的让自己优先级
在前的地点成为最终目的地。例如
6 5 
4 3 5 2 1 0 
4 1 5 0 2 3 
3 1 5 4 0 2 
3 1 2 4 0 5 
5 1 2 0 4 3 
0 3 2 4 1 5
先考虑假如之前的四个地方都没通过，那给5投票时，每个人只需和0（家里蹲）比较。
自然第一个人 5优先级在0前，故投一票，第二个同理，此刻投票地点优先级在前，
则投票，在后则反对不投。最终4票过半，地点5投票成功。
第二轮对地点4投票，此时只需和5比较优先级。规则同上，
此刻优先级 比较 当前最优解优先级。因为出题人假设每个人是聪明的，
即使对于第6个人，家里蹲0的优先级最高，可当投票进行到地点4他依然会给4投支持票，
因为即使把4pass掉，5也会选中，还是轮不到家里顿0，因此聪明的人退而求其次，
把票投给了4.
好了，思路清楚了，这题就非常好做，贴上AC代码，抛砖引玉。*/
#include<iostream>
using namespace std;
int n,k,kk;
void PD(int a[1000][1000],int mk){
    int vote=0,i,j;
    for(i=0;i<n;i++){
        if(a[i][mk] < a[i][kk])
            vote++;
    }
    if( vote > n/2 )
        kk = mk;
}
int main(){
    while( cin >> n >> k ){
        int i,j,temp,a[1000][1000];
        for(i=0;i<n;i++){
            for(j=0;j<k+1;j++){
                cin >> temp;
                a[i][temp] = j;
            }
        }
        kk =0 ;
        for(i=k;i>0;i--)
            PD(a,i);
        if(kk == 0)
            cout <<"otaku"<<endl;
        else
            cout <<kk<<endl;
    }
}

def vote(a):
    global con
    vote = 0
    for i in range(0,n):
        if lst[i][a]<lst[i][con]:
            vote+=1
    if vote>n//2:
        con = a
try:
    while True:
#        lst = np.zeros((1001,1001),dtype=np.int)
        n,k = map(int,input().split())
        lst,con = [[0 for i in range(0,k+1)] for i in range(0,n)],0
        for i in range(0,n):
            tem = list(map(int,input().split()))
            for j in range(0,k+1):
                lst[i][tem[j]] = j     
        for i in range(k,0,-1):
            vote(i)
        if con==0:
            print('otaku')
        else:
            print(con)      
except:
    pass

讲道理，题目是个啥意思啊！！！啊啊啊，英语不好是个硬伤啊！

#Python版

# -*- coding:utf-8 -*-
import sys


def isOk(nums, n, ans, ks):
    cnt = 0
    for i in range(n):
        if nums[i][ks] < nums[i][ans] :
            cnt +=1
    if cnt > n/2:
        return True
    return False

if __name__ == '__main__':
    while 1:
        nk = sys.stdin.readline().strip()
        if not nk:
            break
        n,k =[int(i) for i in nk.split(' ')]
        nums =[[0]*(k+1) for i in range(n)]
        for i in range(n):
            places = [int(j) for j in sys.stdin.readline().strip().split(' ')]
            for ind,v in enumerate(places):
                nums[i][v] = ind
        ans = 0
        for ks in range(k,0,-1):
            if isOk(nums,n,ans,ks):
                ans = ks
        if ans ==0:
            print 'otaku'
        else:
            print ans

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

int selectP(int N,int K){
    vector<vector<int> > v;
    v.reserve(N);
    int m;
    for(int i=0;i<N;++i){
        vector<int> vv;
        vv.reserve(K+1);
        for(int j=0;j<K+1;++j){
            cin>>m;
            vv.push_back(m);
        }
        v.push_back(vv);
    }
    vector<int> cont(K+1,0);
    for(int i=0;i<N;++i){
        for(int j=0;j<K+1;++j){
            if(v[i][j]>0){
                if(++cont[v[i][j]]>=(N/2+1))
                    return v[i][j];
            }
            else
                break;
        }
    }
    return 0;
}

int main()
{
    int N,K;
    cin>>N>>K;
    int m = selectP(N,K);
    if(m)
        cout<<m;
    else
        cout<<"otaku";
    return 0;
}

测试用例:
6 1
0 1
1 0
1 0
0 1
0 1
1 0

对应输出应该为:
otaku

你的输出为:

Q

/* 关键是要模拟投票过程，并且要从后往前想，从第K次投票开始往前推，可以逐级确定每一轮投票的结果，有点递归地思想
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader stdin = new BufferedReader(new InputStreamReader(
				System.in));
		String str = stdin.readLine();
		while (str != null && str.length() > 0) {
			String[] ss = str.split(" ");
			int N = Integer.parseInt(ss[0]);
			int K = Integer.parseInt(ss[1]);
			int[][] favor = new int[N][K + 1];//favor[i][j]表示第i個人对第j个景点的喜欢程度，值越小表示越喜欢
			for (int i = 0; i < N; i++) {
				str = stdin.readLine();
				ss = str.split(" ");
				for (int j = 0; j < K + 1; j++) {
					favor[i][Integer.parseInt(ss[j])] =j ;
				}
			}
			int votes=0;
			//从最后一轮投票开始往回找，因为到了后面没有别的选择了，每个人可以清楚自己是否投票，有点递归的思想
			int finalChoice=0;
			for(int i=K;i>=1;i--){
				votes=0;
				for(int j=0;j<N;j++){
					//比较每一个人对当前方案和下一方案的喜欢程度，来决定是否投票
					if(favor[j][i]<favor[j][finalChoice]){
						votes++;
					}
				}
				if(votes>N-votes){//投票超过一半，更新最终方案
					finalChoice=i;
				}
			}
			if(finalChoice==0){
				System.out.println("otaku");
			}else{
				System.out.println(finalChoice);
			}
			str = stdin.readLine();
		}
	}
}

//综合了Ghost和胡磊的思路，采用从后往前推的方法，
//在本地电脑C-Free5.0编译器可以通过运行,但是网上提交，出现了和牛客560236号相同的问题：
//测试用例:
//6 1
//0 1
//1 0
//1 0
//0 1
//0 1
//1 0
//
//对应输出应该为:
//otaku
//
//你的输出为:
//(无输出？？但在本地编译器上可以输出otaku）
//
#include<stdio.h>

}

#include<iostream>
#include<stdlib.h>
#include<vector>
using namespace std;
int main() {
 int n, k;
 cin >> n >> k;
 vector<vector<int>> survey(n, vector<int>(k + 1, 0));
 vector<int> p(k + 1, 0);
 int i, j, m;

 for (i = 0; i < n; i++) {
  bool z = false;
  for (j = 0; j < k + 1; j++) {
   cin >> m;
   survey[i][j] = m;
   if (z == false) {
    if (m == 0)
     z = true;
    else {
     p[m]++;
    }
   }   
  }
 }
 vector<bool> pp(k + 1, false);
 for (i = 1; i <=k; i++) {
  if (p[i] / (double)n > 0.5) {
   pp[i] = true;
  }
 }

 for (i = n - 1; i >= 0; i--) {
  j = 0;
  
  while (j < k + 1 && survey[i][j] != 0) {
   if (pp[survey[i][j]] == false)
    survey[i][j] = -1;
   j++;
   
  }
  
 }
 vector<int> count(k+1, 0);
 for (i = 1;i<= k; i++) {
  int t = 0;
  if (pp[i] == true) {
   for (j = n-1; j >=0; j--) {
    
    m = 0;
    for (; m < k + 1; m++) {
     if (survey[j][m] == 0) {
      break;
     }
     if (survey[j][m] == i) {

      t++;
      survey[j][m] = -1;
      break;
     }
     else {
      if (survey[j][m] > i)
       break;
     }
    } 
   }
   if ((double)t / n > 0.5) {
    cout << i << endl;
    break;
   }
  }
 }
 if (i > k)
  cout << "otaku" << endl;
 system("pause");
 return 0;
}
数组越界的问题怎么解决？ 

这是什么问题？我用了网上的编译器，output是正确的。为什么这里显示没有output？

测试用例:
6 1
0 1
1 0
1 0
0 1
0 1
1 0

对应输出应该为:
otaku

你的输出为:



import java.util.Scanner;
import java.io.*;
    
public class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
          
        int N = in.nextInt();
        int K = in.nextInt();
 
        int[][] priorityMaps = new int[N][K+1];
 
        for(int i=0; i<N; i++) {
            for(int j=0; j<=K; j++) {
                int priorityIndex = in.nextInt();
                priorityMaps[i][priorityIndex] = j;
            }
        }
 
        int candidate = 0;
        for(int i=K; i>0; i--) {
            int votes = 0;
            for(int j =0; j<N; j++) {
                if(priorityMaps[j][i] < priorityMaps[j][candidate]) {
                    votes++;
                }
            }
            if(votes > N/2) {
                candidate = i;
            }
        }
        if(candidate == 0) {
            System.out.print("otaku");
        } else {
        	System.out.print(candidate);
        }
    }
}

"otaku" 有一个点输出是这个，答案也是这个，但是却报错了