The Android University ACM Team Selection Contest
Time Limit: 1000MS Memory limit: 65536K
题目描述
To be selected, one team has to solve at least one problem in the contest. The the top M teams who solved at least one problem are selected (If there are less than M teams solving at least one problem, they are all selected).
There is an bonus for the girls - if top M teams contains no all-girls teams,the highest ranked all-girls team is also selected (together with the M top teams), provided that they have solved at least one problem.
Recall that in an ACM/ICPC style contest, teams are ranked as following:
1. The more problems a team solves, the higher order it has.
2. If multiple teams have the same number of solved problems, a team with a smaller penalty value has a higher order than a team with a
larger penalty value.
Given the number of teams N, the number M defined above, and each team's name, number of solved problems, penalty value and whether it's an all-girls team, you are required to write a program to find out which teams are selected.
输入
Each test case begins with a line contains two integers, N (1 <= N <=10^4) and M (1 <= M <= N), separated by a single space. Next will be N lines, each of which gives the information about one specific competing team.Each of the N lines contains a string S (with length at most 30, and consists of upper and lower case alphabetic characters) followed by three integers, A(0 <= A <= 10), T (0 <= T <= 10) and P (0 <= P <= 5000), where S is the name of the team, A indicates whether the team is an all-girls team (it is not an all-girls team if Ai is 0, otherwise it is an all-girls team). T is the number of problems the team solved, and P is the penalty value of the team.
The input guarantees that no two teams who solved at least one problem have both the same T and P.
输出
示例输入
35 3AU001 0 0 0AU002 1 1 200AU003 1 1 30AU004 0 5 500AU005 0 7 10002 1BOYS 0 10 1200GIRLS 10 1 2903 3red 0 0 0green 0 0 0blue 0 1 30
示例输出
Case 1:AU003AU004AU005Case 2:BOYSGIRLSCase 3:blue33
这道题是类似于模拟题吧，这套题目有两个模拟类型。
只要细心仔细，把每一个状态都想好，一遍AC不是梦。
题意就是模拟ACM比赛排名，
在一些队伍中选择几个队伍获奖。
这道题有几个注意点：
①只有做出题目的队伍，才能获奖。
②如果选出获奖的队伍中没有女生队伍，那么要将所有女队中排名第一的也要给奖。
③获奖排名，按照输入时的顺序输出队名。
④如果获奖队伍不够，先输出获奖的队伍，剩下的空缺用，奖项数量来代替输出。
例如最后一个样例：只有blue获奖，但是要选出3个队伍，所以剩下两个空缺，用3来代替输出。
⑤是否是女队，用bool型存储可以，但不能直接赋值给该类型，
比如： bool b；cin>>b;
输入10，则会出错。可以设置一个int型来输入，再强制转换类型。
例如： bool b;int t; cin>>t; b=bool(t);
其他的事项，在代码中有注释。
#include <iostream>#include <algorithm>#include <string>#include <string.h>using namespace std;struct Team{ string name; bool isgirl; int aproblem,atime,num;}team[10010];int n,m,total;// 按照AC题目多少与时间排序bool cmp_a(Team a,Team b){ if(a.aproblem==b.aproblem) { if(a.atime<b.atime) return 1; else return 0; } else return a.aproblem>b.aproblem;}// 按序号大小排序bool cmp_num(Team a,Team b){ return a.num<b.num;}// 判断前m个队伍中是否有女队bool have_girl(void){ int i; for(i=0;i<m;++i) if(team[i].isgirl) return true; return false;}int main(){ Team temp; int i,k,test,te; cin>>test; for(k=1;k<=test;++k) {// memset(team,0,sizeof(team)); // 输入 cin>>n>>m; total=0; for(i=0;i<n;++i) { cin>>temp.name>>te>>temp.aproblem>>temp.atime; // 一道题没答出来，舍掉 if(!temp.aproblem) continue; team[total].name=temp.name; team[total].isgirl=bool(te); team[total].aproblem=temp.aproblem; team[total].atime=temp.atime; team[total].num=i+1; ++total; } // 排序 sort(team,team+total,cmp_a); // 输出 cout<<"Case "<<k<<":"<<endl; // 如果做出题目的队伍数量不足M个 if(total<=m) { sort(team,team+total,cmp_num); for(i=0;i<total;++i) cout<<team[i].name<<endl; for(;i<m;++i) cout<<m<<endl; cout<<endl; continue; } // 如果前m个队伍中没有女队 if( !have_girl() ) { for(i=m;i<total;++i) { if(team[i].isgirl) { team[m].name=team[i].name; team[m].num=team[i].num; break; } } sort(team,team+m+1,cmp_num); for(i=0;i<=m;++i) cout<<team[i].name<<endl; cout<<endl; } else { sort(team,team+m,cmp_num); for(i=0;i<m;++i) cout<<team[i].name<<endl; cout<<endl; } } return 0;}