1025 PAT Ranking (25分) 思路分析 +滿分代碼

題目

Programming Ability Test (PAT) is organized by the College of Computer Science and Technology of Zhejiang University. Each test is supposed to run simultaneously in several places, and the ranklists will be merged immediately after the test. Now it is your job to write a program to correctly merge all the ranklists and generate the final rank.

Input Specification:
Each input file contains one test case. For each case, the first line contains a positive number N (≤100), the number of test locations. Then N ranklists follow, each starts with a line containing a positive integer K (≤300), the number of testees, and then K lines containing the registration number (a 13-digit number) and the total score of each testee. All the numbers in a line are separated by a space.

Output Specification:
For each test case, first print in one line the total number of testees. Then print the final ranklist in the following format:

registration_number final_rank location_number local_rank
The locations are numbered from 1 to N. The output must be sorted in nondecreasing order of the final ranks. The testees with the same score must have the same rank, and the output must be sorted in nondecreasing order of their registration numbers.

Sample Input:
2
5
1234567890001 95
1234567890005 100
1234567890003 95
1234567890002 77
1234567890004 85
4
1234567890013 65
1234567890011 25
1234567890014 100
1234567890012 85
Sample Output:
9
1234567890005 1 1 1
1234567890014 1 2 1
1234567890001 3 1 2
1234567890003 3 1 2
1234567890004 5 1 4
1234567890012 5 2 2
1234567890002 7 1 5
1234567890013 8 2 3
1234567890011 9 2 4

題目解讀

這題看的我真費勁，英語硬傷啊，不過看懂題目之後發現這題一點都不難啊，大概意思是說：給出n個考場，給出每個考場內的考生數目m、考生的編號、分數，讓最終輸出考生的最終排名，輸出格式是：編號總排名考場號考場內排名，要求排名是按照分數從高到底到底，如果分數一樣就並列，但是要學號小的在前。

注意點：

學生編號是 13 位數字，最後輸出也一定要是13位，不足13位補前導0。
假如 a b 分數相同，之後是 c d分數相同，排名是 1 1 3 3，而不是 1 1 2 2，也就是說，第二個人他把那個位置佔了，但是排名要和他前面那個人保持一致。

思路分析

構建按結構體 Student 存儲考試信息：因為編號是13位數字，所以不能用int，可以用 long long 或者 char[] 或者 string，但因為編號也要用於排序，字符串數組排序需要逐個比較字符，速度較慢，所以我們直接用 long long 存儲了，直接比大小
用vector<Student> total_stu 保存全部學生信息，用 vector<Student> local_stu 保存考場內學生信息。
考場號按順序編號 1-N，沒讀入一個考場的學生信息，就先按分數排名，得到考場內排名 stu[i].local_rank，注意分數相同排名相同，然後將其移入 total_stu。
多個考場考生信息全部統計完後，對 total_stu 進行排序，得到每個考生的最終排名，同樣需要調整分數相同排名相同。
最後，輸出考生數目（total_stu.size())，輸出每個考生信息。

滿分代碼

注意輸出編號一定要是 printf(“%013lld”, stu[i].no)，不然你最後一個用例過不了。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// 考生信息
struct Student {
    // 編號 13位數字
    // string no; // 字符串排名需要逐個比較字符，速度慢，這裡用空間換時間
    long long no;
    // 分數 最終排名 考場號 考場內排名
    int score, final_rank, local_number, local_rank;
};

// 按分數降序
bool cmp(Student a, Student b) {
    return a.score != b.score ? a.score > b.score : a.no < b.no;
}

int main() {

    // N個考場，考場內M個考生
    int n, m;
    cin >> n;
    // 保存全部考生信息
    vector<Student> total_stu;
    for (int i = 1; i <= n; ++i) {
        // 當前考場 m 人
        cin >> m;
        // 保存當前考場考生信息
        vector<Student> local_stu(m);
        for (int j = 0; j < m; ++j) {
            // 學號和分數
            cin >> local_stu[j].no >> local_stu[j].score;
            // 當前考場號
            local_stu[j].local_number = i;
        }
        // 考場內按分數排名
        sort(local_stu.begin(), local_stu.end(), cmp);
        // 設置考場內排名，成績相同排名應該一樣，
        // 再將當前考場內考生信息加入全部信息集合
        local_stu[0].local_rank = 1;
        total_stu.push_back(local_stu[0]);
        for (int j = 1; j < m; ++j) {
            // 並列
            if (local_stu[j].score == local_stu[j - 1].score)
                local_stu[j].local_rank = local_stu[j - 1].local_rank;
            // 注意這裡是 j + 1，不是 local_stu[j - 1].local_rank + 1
            // 因為排名是 1 1 3 4 4 6 這樣的規則
            else 
                local_stu[j].local_rank = j + 1;
            // 將他加入全部信息的集合
            total_stu.push_back(local_stu[j]);
        }
    }
    // 再對全部學生按成績降序排名，得到考生的最終排名
    sort(total_stu.begin(), total_stu.end(), cmp);
    // 設置最終排名
    total_stu[0].final_rank = 1;
    for (int j = 1; j < total_stu.size(); ++j) {
        // 並列
        if (total_stu[j].score == total_stu[j - 1].score)
            total_stu[j].final_rank = total_stu[j - 1].final_rank;
        else 
            total_stu[j].final_rank = j + 1;
    }

    // 輸出全部考生數目
    cout << total_stu.size() << endl;
    // 輸出每個考生的 編號 總排名 考場號 考場內排名
    // 注意編號要13位輸出
    for(int i = 0; i < total_stu.size(); i++)
        printf("%013lld %d %d %d\n", total_stu[i].no, total_stu[i].final_rank, total_stu[i].local_number, total_stu[i].local_rank);

    return 0;
}

Tags: C/C++ C++ PTA 數據結構與算法算法與數據結構