## Thursday, July 28, 2016

### hihocoder 1154 Spring Outing - [微软2016校园招聘在线笔试第二场]

hihocoder 1154 Spring Outing - Pat - 博客园
You class are planning for a spring outing. $N$$N$ people are voting for a destination out of $K$$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, 1, ... K$. ($0$$0$ is for staying at home.) For example, when $K=3$$K=3$, preference "$1,0,2,3$$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$$N$ and $K$$K$, the number of people in your class and the number of candidate places.
The next $N$$N$ lines each contain a permutation of $0$$0$ ~$K$$K$, representing someone's preference.
For 40% of the data, $1\le N,K\le 10$$1 \le N, K \le 10$
For 100% of the data, $1\le N,K\le 1000$$1 \le N, K \le 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.

2 2 1 0 2 2 1 0

1
http://www.ghosta3.com/blog/?p=91

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

1、当对p2投票时，学生s1明显选择家里蹲也不会选择去地点p2
2、因此我们知道了对p2的投票结果，回到p1，如果2投X票的话，那么会造成家里蹲的结果。

https://glatue.wordpress.com/2016/02/25/hihocoder-1154-spring-outing/
N个人选K个地点，每个人都有自己的优先级，还可以选择在家。题目是每个人都事先知道了其他人的选择优先级，问大家都“非常聪明”的情况下，应该怎么选？

 int N, K; int choose(vector> &ranks, int now, int prev) {     int cnt = 0;     for (int i = 0; i < N; i++)         cnt += (ranks[i][now] < ranks[i][prev]);     return cnt * 2 <= N ? prev : now; } int main() {     //freopen("t.txt", "r", stdin);     cin >> N >> K;     vector> ranks(N, vector<int>(K + 1, 0));     for (int i = 0; i < N; i++)     for (int j = 0; j < K + 1; j++)     {         int x;         scanf("%d", &x);         ranks[i][x] = j;     }     vector<int> result(K + 2);     result[K + 1] = 0;     for (int i = K; i >= 1; i--)         result[i] = choose(ranks, i, result[i + 1]);           if (0 == result[1])         cout << "otaku" << endl;     else         cout << result[1] << endl;           return 0; }
http://hihocoder.com/discuss/question/2819/
result = 0
For i = m .. 1
vote = 0
For j = 1 .. n
If (rank[j][i] < rank[j][result]) Then
vote = vote + 1
End If
End For
If (vote > n / 2) Then
result = i
End If
End For


Read full article from hihocoder 1154 Spring Outing - Pat - 博客园