e788: b3.畢業典禮(Ceremony) TOI練習賽 解題心得

第一行輸入一個正整數N(1≤ N ≤ 100)，表示共有幾位學生；接著輸入N行，每行皆有一個學號IDID為9個字元，由8個數字與一個英文大寫字母所組成）及英文姓名s（1≤ |s|≤ 10，即姓名不超過10個字元），ID與s中間以空白區隔。

學務處已收到所有報名參加畢業典禮的學生學號，需要你協助撰寫一個程式來列出學生上台的順序表。

※上台規則如下：

1、依照學院代碼A~Z的順序。

2、若學院代碼相同，依學號開頭由小到大，4(學士)à6(碩士) à8 (博士)。

3、若學院代碼、學號開頭皆相同，則依報名順序排列。

這題就是標準準的大數據排序，看題目大概就猜得出不是我最愛的氣泡排序可以搞定，所以這題就是改用二元搜尋法來解決。這題要注意的是排序有兩個條件，所以在二元搜尋法的使用上需要有一些改變。

如果還是有什麼不清楚的地方，歡迎留言或來信，我會做更進一步的解釋。

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
    cin.tie(0), cin.sync_with_stdio(false);
    cout.tie(0), cout.sync_with_stdio(false);
    vector<string> v;
    string s;
    int n;
    cin >> n;
    getline(cin, s);
    for (int x = 0; x < n; x++) {
        getline(cin, s);
        bool find = false;
        int start = 0, end = x, mid = (start + end) >> 1;
        while (mid != start) {
            if (s[8] < v[mid][8]) {
                end = mid;
            }
            else if (s[8] > v[mid][8]) {
                start = mid;
            }
            else {
                int j = mid;
                while (true) {
                    if (j == -1) {
                        break;
                    }
                    if (s[8] == v[j][8]) {
                        j--;
                    }
                    else {
                        break;
                    }
                }
                j++;
                while (true) {
                    if (j == x || s[8] != v[j][8] || s[0] < v[j][0]) {
                        mid = j;
                        find = true;
                        break;
                    }
                    j++;
                }
            }
            if (find)  break;
            mid = (start + end) >> 1;
        }
        if (find) {
            v.insert(v.begin() + mid, s);
        }
        else if (v.size() > mid) {
            if ((v[mid][8] == s[8] && v[mid][0] <= s[0] ) || v[mid][8] < s[8]) {
                v.insert(v.begin() + mid +1, s);
            } else
                v.insert(v.begin() + mid, s);
        }
        else {
            v.push_back(s);
        }
    }
    for (int i = 0; i < v.size(); i++) {
        cout << v[i][8] << ":" << v[i].substr(9, 100) << endl;
    }


    return 0;
}