HDU 1338 Game Prediction

HDU 1338 Game Prediction

這題我用的是貪心算法，我的理解是這樣的：

要求我最少能贏的次數，就是求別人最多能贏的次數。首先把我的牌先升序排序，然後我從小開始出，對於我出的牌，別人應該盡可能的壓，而且用他們比我大的最小的那張牌；如果他們不壓，那麼他們後面這張牌就很有可能用不上，就少贏一次。

#include
#include
#include
#include
#include
#include
using namespace std;
int card[52];
bool used[1002];
int n,m,t;
int _find(int x)
{
    for(int i=x+1;i<=t;i++)
        if(!used[i])
        return i;
    return 0;
}
int main()
{
    int k=1;
    while(scanf("%d%d",&m,&n))
    {
        if(n==0&&m==0)
            break;
        memset(used,false,sizeof(used));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&card[i]);
            used[card[i]]=true;
        }
        sort(card+1,card+n+1);
        t=n*m;
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            int a=_find(card[i]);
            //printf("card=%d,a=%d\n",card[i],a);
            if(a!=0)
                used[a]=true;
            else
            {
                ans+=n-i+1;
                break;
            }
        }
        printf("Case %d: %d\n",k++,ans);
    }
    return 0;
}