PAT 解题报告 1025. PAT Ranking (25)

题目描述:

给你N个PAT用户的成绩列表, 要你求得每个用户的local 排名 (i.e., 该用户在该列表里面的排名)和全局排名, (i.e., 该用户在所有列表里面的总排名).

算法分析:

算法是先给每个列表的用户排序, 求得用户的local排名记录在结构体里面, 然后对整体排名求得全局排名, 整体排序的时候可以直接调用库函数进行排序, 但是这样其实有所浪费, 因为之前那N个列表都已经排序好了, 那么进行全局排序的时候可以利用merge sort的思想做到一个线性算法: Merge N sorted list.

注意点:

注意PAT的排名规则: A, B, C, D, E, 如果A, B并列第一, 那么排名是A(1), B(1), C(3), D(4), E(5), 而不是A(1), B(1), C(2), D(3), E(4).

Written on July 29, 2013