首页 > 代码库 > PAT 1025 PAT Ranking
PAT 1025 PAT Ranking
#include <cstdio>#include <cstdlib>#include <vector>#include <cstring>#include <queue>#include <algorithm>using namespace std;class Man {public: char id[14]; int location; int score; int local_rank;};class RankCmp{public: bool operator () (const Man* a, const Man* b) { if (a->score > b->score) { return true; } else if (a->score < b->score) { return false; } return strcmp(a->id, b->id) < 0; }};void do_local_rank(vector<Man*> &v) { int len = v.size(); if (len < 1) return; int last_score = v[0]->score; v[0]->local_rank = 1; for (int i=1; i<len; i++) { Man& cur = *v[i]; if (cur.score != last_score) { cur.local_rank = i + 1; last_score = cur.score; } else { cur.local_rank = v[i - 1]->local_rank; } }}void print(vector<Man*> &v) { int len = v.size(); for (int i=0; i<len; i++) { printf("%s %d %d\n", v[i]->id, v[i]->score, v[i]->local_rank); }}int main() { int N, K, total = 0; scanf("%d", &N); vector<vector<Man*> > locations(N); Man tmp; RankCmp rankcmp; for (int i=0; i<N; i++) { scanf("%d", &K); for (int j=0; j<K; j++) { total++; scanf("%s%d", tmp.id, &(tmp.score)); tmp.location = i + 1; locations[i].push_back(new Man(tmp)); } sort(locations[i].begin(), locations[i].end(), rankcmp); do_local_rank(locations[i]); } printf("%d\n", total); vector<Man*> all; for (int i=0; i<N; i++) { all.insert(all.end(), locations[i].begin(), locations[i].end()); } sort(all.begin(), all.end(), rankcmp); int last_rank = 0, last_score = -1; for (int i=0; i<total; i++) { Man& cur = *all[i]; if (cur.score != last_score) { last_score = cur.score; last_rank = i + 1; } printf("%s %d %d %d\n", cur.id, last_rank, cur.location, cur.local_rank); } return 0;}
最后一个全局排序300 * 100 log(300 * 100),如果用优先队列可以变为300 * 100 log(100),提升也不大,可能还是出现下降
PAT 1025 PAT Ranking
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。