题目

源地址:

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

理解

最优的方法是出一张比你出的牌大的牌中最小的牌,不过没有严格证明= =。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;
const int maxn = 1001;

int vis[maxn], a[maxn];
int n, m;

int main(int argc, char const *argv[])
{
    int t = 0;
    while (cin >> n >> m)
    {
        if (m == 0 && n == 0) break;
        t++;
        memset(vis, 0, sizeof(vis));
        for (int i = 1; i <= m; i++)
        {
            cin >> a[i];
            vis[a[i]] = 1;
        }
        sort(a + 1, a + m + 1);
        bool flag;
        int j = 1;
        int amount = 0;
        for (int i = 1; i <= m; i++)
        {
            flag = false;
            for (; j <= n * m; j++)
            {
                if (!vis[j] && j > a[i])
                {
                    flag = true;
                    j++;
                    break;
                }
            }
            if (flag) amount++;
        }
        printf("Case %d: %d\n", t, m - amount);
    }
    return 0;
}

更新日志

  • 2014年08月12日 已AC。