2014
01-05

# Ranking

Hosting a programming contest is fun, but it’s also a lot of work. For instance, at the end of the day the jury will have to create a ranking of the teams based on their results during the contest. This can be tedious to do by hand, so we would like you to write a program for this task.

For the BAPC, the rules for the ranking are as follows:

Teams are ranked according to the most problems solved; teams tied are ordered by increasing total time used.

The time used for a problem is the number of minutes between the start of the contest and the first accepted run, plus a 20 minute penalty for each rejected run until the first accepted run.

The total time used is the sum of the times used for each problem solved (as described above). Note that penalty time for problems for which no run was accepted does not count toward the total time used.

If ties remain at the end of the contest, the point of comparison between tied teams will be the last point in time where their scores differed (e.g. if two teams are tied at the end of the contest, the team which solved their last problem earlier than the other team solved their last problem wins).

During the contest, teams submit solutions for problems, which are processed by the jury as runs. Each run has four properties:

the submission time in minutes since the beginning of the contest (an integer between 1 and 300, inclusive);

the name of the team that submitted the solution (a non-empty string of at most 20 lower-case letters);

the identifier of the corresponding problem (an upper-case letter A through J, inclusive);

the result as determined by the judging software (either accepted or rejected).

At the end of the contest, we have a list of runs available (ordered by non-decreasing submission times) and we want you to determine the final ranking of the teams.

Teams that are tied will share a position; those teams should be ordered alphabetically in the results.

On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

one line with the number of teams t (1 <= t <= 50) and the number of runs r (0 <= r <= 5 000), seperated by a single space;

then t lines, each with the name of a team;

then r lines, each with the description of a run: time, team, problem and result, formatted as described above, and seperated by a single space.

On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

one line with the number of teams t (1 <= t <= 50) and the number of runs r (0 <= r <= 5 000), seperated by a single space;

then t lines, each with the name of a team;

then r lines, each with the description of a run: time, team, problem and result, formatted as described above, and seperated by a single space.

1
8 28
twente
utrecht
groningen
amsterdam
eindhoven
leiden
delft
nijmegen
5 utrecht B rejected
8 eindhoven F accepted
10 utrecht F accepted
17 utrecht B rejected
18 leiden C rejected
23 twente F rejected
25 utrecht B accepted
26 amsterdam D rejected
27 amsterdam D accepted
27 leiden C accepted
27 groningen F accepted
28 twente F rejected
30 nijmegen C rejected
30 nijmegen C accepted
30 delft B accepted
30 delft B rejected
33 twente F accepted
47 groningen D rejected
51 leiden D accepted
51 amsterdam C accepted
51 groningen D accepted
60 utrecht D accepted
65 utrecht J accepted
67 twente F rejected
70 twente F accepted
90 eindhoven D accepted
100 utrecht A rejected
101 utrecht C rejected

1 utrecht 4 200
2 groningen 2 98
3 amsterdam 2 98
3 leiden 2 98
5 eindhoven 2 98
6 delft 1 30
7 nijmegen 1 50
8 twente 1 73

ACM比赛排名，排名规则如下：

1、按A题数（降序）

2、题数相同按总时间（升序）

3、

①最后A掉的那一题的时间，不包括罚时（升序）

②最后A掉的那一题的时间，包括罚时（降序）

3、递归前一题，直道最后一题

4、以上都符合，队名按字典排序（升序）

//AC CODE：

#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<map>
using namespace std;

int cas,t,r;
struct Team
{
char name[25];
int pid[15];
int pid_fs[15];
int icount;
int tol_time;
int a[15],fa[15];//从1开始
} team[55];
int findTeam(char xx[])
{
for(int i=0; i<t; i++)
if(strcmp(xx,team[i].name)==0)
return i;
return -1;
}
int cmp( const void *a , const void *b )
{
struct Team *c = (Team *)a;
struct Team *d = (Team *)b;
if(c->icount != d->icount)
return d->icount - c->icount;//总题数降序
else if(c->tol_time!=d->tol_time)
return c->tol_time - d->tol_time;//总时间升序
else
{
for(int i=c->icount; i>=1; i--)
{
if(c->a[i] != d->a[i])
return c->a[i] - d->a[i];//A题时间升序
else if(c->fa[i] != d->fa[i])
return d->fa[i] - c->fa[i];//A题+罚时降序
}
}
return strcmp(c->name,d->name);
}
void print()
{
printf("1 %s %d %d\n",team[0].name,team[0].icount,team[0].tol_time);
int c1=1,c2=1;
for(int i=1; i<t; i++)
{
if(team[i-1].icount==team[i].icount)
{
if(team[i-1].tol_time==team[i].tol_time)
{
for(int j=team[i].icount; j>=1; j--)
{
if(team[i-1].a[j]==team[i].a[j])
{
if(team[i-1].fa[j]==team[i].fa[j])
{
;
}
else
{
c1=c1+c2;
printf("%d %s %d %d\n",c1,team[i].name,team[i].icount,team[i].tol_time);
c2=1;
goto to;
}
}
else
{
c1=c1+c2;
printf("%d %s %d %d\n",c1,team[i].name,team[i].icount,team[i].tol_time);
c2=1;
goto to;
}
}
c2++;
printf("%d %s %d %d\n",c1,team[i].name,team[i].icount,team[i].tol_time);
to:
;
}
else
{
c1=c1+c2;
printf("%d %s %d %d\n",c1,team[i].name,team[i].icount,team[i].tol_time);
c2=1;
}
}
else
{
c1=c1+c2;
printf("%d %s %d %d\n",c1,team[i].name,team[i].icount,team[i].tol_time);
c2=1;
}
}
}
int main()
{
//freopen("in.txt", "r", stdin);
scanf("%d",&cas);
int ti,index,id;
char name[25],res[15],ch;
while(cas--)
{
scanf("%d %d",&t,&r);
for(int i=0; i<t; i++)
{
scanf("%s",team[i].name);
team[i].tol_time=0;
team[i].icount=0;
for(int j=0; j<15; j++)
{
team[i].pid[j]=0;
team[i].pid_fs[j]=0;
}
}
for(int i=0; i<r; i++)
{
scanf("%d %s %c %s",&ti,name,&ch,res);
if(ti<=300)
{
index=findTeam(name);
if(index==-1)
continue;
id=ch-'A';
if(team[index].pid[id]==1)//已经做出来了
continue;
else
{
if(strcmp(res,"accepted")==0)
{
team[index].tol_time+=ti+team[index].pid_fs[id];
team[index].pid[id]=1;
team[index].icount++;
//
team[index].a[team[index].icount]=ti;
team[index].fa[team[index].icount]=ti+team[index].pid_fs[id];
}
else
{
team[index].pid_fs[id]+=20;
}
}
}
}
qsort(team,t,sizeof(team[0]),cmp);
print();
}
}

1. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

2. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
O(n) = O(n-1) + O(n-2) + ….
O(n-1) = O(n-2) + O(n-3)+ …
O(n) – O(n-1) = O(n-1)
O(n) = 2O(n-1)

3. 这道题目虽然简单，但是小编做的很到位，应该会给很多人启发吧！对于面试当中不给开辟额外空间的问题不是绝对的，实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟，今天看到小编这篇文章相见恨晚。