题目链接:http://poj.org/problem?id=1323
题目意思:有n个人,每个人手上有m张牌,每张牌上写着1--n*m之间的一个不同数字,n个人拿着他们手中的牌做游戏,每一轮每一个人拿出一张牌,此轮拿出的牌上的数字最大的那人获得本轮胜利,现在告诉你你自己手中的m张牌上的数字,问你在这m轮中至少可以获得几轮胜利!!
思路:将除了你自己手中牌的数字的其他最大的m个数字的牌给予另一个人,即给予该人一副最优的牌,接下来就是判断你和这个人玩这个游戏,你至少能获胜几轮。
代码:
#include<stdio.h> #include<string.h> #include<stdlib.h> int me[60],other[60]; int used[10050]; int n,m; int Case=0,ans; int cmp(const void *a,const void *b) { return *(int *)a - *(int *)b; } int main() { int i,j; while(scanf("%d%d",&n,&m) && n!=0 ) { ans=0; Case++; memset(used,0,sizeof(used)); for(i=0;i<m;i++) { scanf("%d",&me[i]); used[me[i]]=1; } for(i=n*m,j=0;j<m;i--)//给予某个人一副最优的牌 { if(!used[i]) { other[j]=i; used[other[j]]=1; j++; } } qsort(me,m,sizeof(me[0]),cmp); qsort(other,m,sizeof(other[0]),cmp); for(i=m-1;i>=0;i--)//你从大出道小,而另一个人只需要出他手中的比你大的牌中的最小的一张,即该轮你是输的 { for(j=0;j<m;j++) { if(other[j]>me[i] && used[other[j]]) { used[other[j]]=0; break; } } } for(i=0;i<m;i++)//判断那一个人输的次数,也就是你赢的次数 if(used[other[i]]) ans++; printf("Case %d: %d\n",Case,ans); } }