题目描述
程序设计竞赛中，OJ系统的排名一般遵循以下规则： 每个参赛者（队伍）都有一个唯一的编号，当比赛结束时， 1) 通过题数较多的排名高； 2) 如果通过题数相同，则总花费时间较少的排名高； 3) 如果经过上面两条后排名仍相同，则按照编号递增排序。 某道题的花费时间为第一次正确提交的时间加上罚时——之前每次错误提交都会增加20分钟的罚时，队伍的总花费时间为所有通过的题目的花费时间之和。 现有一张比赛结束时的提交记录表，依据上述规则给出队伍的排名。提交记录表的格式如下： 队伍编号 问题编号 提交时间（秒） 是否通过 1 2 3000 0 1 2 3100 1 2 1 4200 1 “是否通过“一列中，1表示正确通过，否则为0。假设一共有3只队伍，那么根据上表，队伍1和队伍2各通过1题，队伍3一道题都没能通过。队伍1总花费时间为3100+1200=4300，队伍2总花费时间为4200。因此最终排名为：2，1，3。
输入
第一行为两个整数N、M，分别表示队伍数和提交数。1≤N, M≤1000。 接下来为M行整数，每行为队伍编号n、问题编号p、提交时间t和是否通过r。1≤n≤N, 1≤p≤20, 1≤t≤36000。
输出
N个整数，表示队伍的排名。
样例输入
3 31 2 3000 01 2 3100 12 1 4200 1
样例输出
2 1 3
#include#include #define REC sh[i]using namespace std;struct rec { int t; //team int q; //ques int c; //cost int p; //pass};struct info { int no; //team number int ac; int tt; //total time};bool accmp(const info &a, const info &b){ if (a.ac > b.ac) return true; else return false;}bool ttcmp(const info &a, const info &b){ if (a.tt < b.tt) return true; else return false;}info team[1001];rec sh[1001];int qs[1001][1001];int main(){ //input int n, m; cin >> n >> m; int totalq = 0; for (int i = 1; i <= n; i++) team[i].no = i; for (int i = 0; i < m; i++) { cin >> sh[i].t >> sh[i].q >> sh[i].c >> sh[i].p; totalq = (sh[i].q > totalq ? sh[i].q : totalq); } //init for (int i = 1; i <= totalq; i++) for (int j = 1; j <= n; j++) { qs[i][j] = 0; team[j].tt = 0; team[j].ac = 0; } //dealing for (int i = 0; i < m; i++) { //REC == sh[i] if (REC.p == 0) qs[REC.q][REC.t] += 1; else { team[REC.t].tt += 1200 * qs[REC.q][REC.t] + REC.c; team[REC.t].ac += 1; } } //sort stable_sort(team + 1, team + n+1, ttcmp); stable_sort(team + 1, team + n+1, accmp); //output for (int i = 1; i <= n; i++) { cout << team[i].no; }return 0;}
解题要点：
1.队伍序号在初始化的时候就算排序完毕了，所以接下来只要用稳定的排序方法就可以保证同ac同耗时的时候序号不变了。
1.1.同理，排序好时间以后，稳定排序ac就可以保证同ac的时候耗时顺序不变了。
2.语文很重要：
2.1.一道题的罚时仅在该题通过后计入，所以如果某个队伍某题尝试过很多次都没过，不会导致总用时加上很多个1200
2.2.总耗时不会重置，所以后期会出现某题的计入时间为上万的情况。
2.2.1.也就是说，类似对一题+100000分，罚时-1200这样的权重操作是行不通的……（或许用long long int，一题加上100000000可行？）
更多测试样例与详细数据
//test14 81 2 5400 02 1 5000 12 2 5800 02 2 8800 13 1 3800 03 1 5000 13 2 6000 03 2 7600 1//number of team, amount of ac, total time cost//before sort1 0 02 2 150003 2 150004 0 0//after sort2 2 150003 2 150001 0 04 0 0//test24 71 1 5000 11 2 5400 01 3 7000 12 1 5000 13 1 3800 13 2 8000 14 2 5000 11 2 120002 1 50003 2 118004 1 50003 2 118001 2 120002 1 50004 1 5000