1. 题目

题目链接：Spring Outing 。

题目描述

  You class are planning for a spring outing. N people are voting for a destination out of K candidate places.

  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
3
2 2
1 0 2
2 1 0

输出样例

1
1

2. 题解

分析

由于是从地方 1 ~ K 依次投票，假设当前对地方 i 投票，则每个人对 i 投票与否取决于是否存在地方 j > i，且在当前同学的优先级列表中 preference[j] > preference[i]，即在优先级列表中越靠前。可以看出，一个人的对于当前地方 i 的投票只会收到 > i 的地方的影响，而不会受到 < i 的地方的影响（其实显然，因为对 i 投票说明 < i 的地方都没能去成）。

由于最坏的情况就是哪里都去不成，即回家 0 ，此时不妨逆向思考，我们可以一开始就假设可能去的候选地方为 candidate = 0 ，然后从 K 往 1 遍历逐个判断，第 i 个地方是否可能称为候选地方，如果能够成为候选地方，则更新候选地方为 i 。判断策略如下：

  • 对于每个同学 j ，如果地方 i 的优先级大于地方 candidate，则投票数 vote += 1
  • 对所有同学遍历完上述操作后，如果 vote > N/2 ，则更新 candidate = i

这样一来，就成功消除了后面地方对当前地方投票的影响。因为如果存在一个地方 j > 当前投票地方 i 为候选地方，那么对于投票的每个同学而言，如果其 j 的优先级大于 i ，那么该同学显然不会对 i 投票；否则，该同学就会投票。和上述判断策略的结果一致。由于最遭的情况就是回家，所以 0 始终是候选地方，因此满足了前提假设，然后逐步回溯判断最终即得到答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1005;

int preference[MAXN][MAXN];

int main()
{
    int N, K;
    while(scanf("%d%d", &N, &K) != EOF) {
        for(int i = N; i; --i) {
            for(int j = K; ~j; --j) {
                int x;
                scanf("%d", &x);
                preference[i][x] = j;
            }
        }
        int ans = 0;
        for(int i = K; i; --i) {
            int vote = 0;
            for(int j = N; j; --j) {
                if(preference[j][i] > preference[j][ans]) {
                    ++vote;
                }
            }
            if(vote > N/2) {
                ans = i;
            }
        }
        if(ans == 0) {
            printf("otaku\n");
        } else {
            printf("%d\n", ans);
        }
    }
    return 0;
}