POJ 1323 - Game Prediction

http://poj.org/problem?id=1323

概要

1, 2, ..., M * N と連番の数字が書かれた M * N 枚のカードがある． これを M 人に N 枚ずつ配る．

自分の手札から一枚場に出し，他の人の人の数と比べ，一番大きい札を出した人が勝者である． これを N 回繰り返す．

自分の N 枚の手札が与えられたとき，少なくとも何回勝てるかを答える．

制約

• 2 <= M <= 20
• 1 <= N <= 50

解法

降順にソートして調べる (言葉で説明しにくい…)．

 1 #include <cstdio>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8   int N, M;
 9   for (int Ti = 1; scanf("%d %d", &M, &N) != EOF && M != 0; Ti++) {
10     vector<int> v(N);
11     for (int i = 0; i < N; i++) {
12       scanf("%d", &v[i]);
13     }
14 
15     sort(v.rbegin(), v.rend());
16     int ans = 0;
17     int c = 0;
18     vector<int>::const_iterator it = v.begin();
19     for (int i = N*M; it != v.end(); i--) {
20       if (*it == i) {
21         if (c == 0) {
22           ++ans;
23         } else {
24           --c;
25         }
26         ++it;
27       } else {
28         ++c;
29       }
30     }
31     printf("Case %d: %d\n", Ti, ans);
32   }
33   return 0;
34 }