程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1338 Game Prediction

HDU 1338 Game Prediction

編輯:C++入門知識

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;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved