［原創題］誰來告訴我我能去哪 - 提示、題解

題目簡介

給定學校及學生數量，對於每個學校包含學校正備榜單，對於每個學生有不同的志願序。試求對於學生最理想的狀況下，每個學生能進入的學校。

提示

推薦打開之後想想看再繼續，不要一次使用全部

提示1

配對時可以思考看看學校和學生間的關係？

提示2

應該紀錄學校錄取的人還是學生要去的學校？

題解

點開會有完整解答，請想過後再開喔

思路

這題需要使用Gale–Shapley algorithm（也稱為延遲接受演算法），這演算法不怎麼常見，但其實本身不怎麼複雜。

1. 在還沒有配對但志願還沒用完的人（追求者）中，拉一個人去試試看他的最高志願

   可以使用Queue紀錄需要配對的人

2. 如果接收者
   • 還有空間，那就暫時先把它當錄取
   • 空間已滿，那就嘗試看看能不能把一個人推出去

     用接收者的志願序比較。記得幫被推出去的人安排新歡

重點：不一定要有完全最好的答案，先留下當下最好的答案。

完整程式碼

請注意，本程式碼僅供寫法上參考，直接複製貼上程式碼會導致你學不到任何東西。

C++ 範例程式碼

#include <bits/stdc++.h>
using namespace std;
#define raymondwengcode ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

int main() {
raymondwengcode;

    int m, n;
    cin >> m >> n;
    vector<unordered_map<int, int>> sch(m); // sch[i][j] = student j's place in school i
    vector<int> acceptCnt(m); // acceptCnt[i] = number of students school i can accept
    for (int i = 0; i < m; i++) {
        int a, w;
        cin >> a >> w;
        acceptCnt[i] = a;
        for (int j = 0; j < a+w; j++) {
            int student;
            cin >> student;
            sch[i][student-1] = j;
        }
    }
    vector<vector<int>> stu(n); // stu[i] = list of school preferences for student i
    for (int i = 0; i < n; i++) {
        int k;
        cin >> k;
        stu[i] = vector<int>(k);
        for (int j = 0; j < k; j++) {
            cin >> stu[i][j];
            stu[i][j]--;
        }
    }
    vector<vector<int>> nowAcc(m); // nowAcc[i] = currently accepted students for school i
    vector<int> tried(n, 0); // tried[i] = number of schools student i has tried
    vector<int> ans(n, -2); // ans[i] = assigned school for student i
    queue<int> q; // queue of unassigned students
    for (int i = 0; i < n; i++) {
        q.push(i);
    }
    while (!q.empty()) {
        int student = q.front();
        q.pop();
        if (tried[student] >= stu[student].size()) {
            continue; // no more schools to try
        }
        int school = stu[student][tried[student]];
        tried[student]++;
        if (sch[school].find(student) == sch[school].end()) {
            q.push(student);
            continue; // school does not know this student
        }
        if (nowAcc[school].size() < acceptCnt[school]) {
            nowAcc[school].emplace_back(student);
            ans[student] = school;
        }else {
            int toPut = student;
            for (int j = 0; j < acceptCnt[school]; j++) {
                if (sch[school][nowAcc[school][j]] >= sch[school][toPut]) {
                    ans[toPut] = school;
                    swap(toPut, nowAcc[school][j]);
                }
            }
            ans[toPut] = -2;
            q.push(toPut);
        }

    }
    for (int i = 0; i < n; i++) {
        cout << i+1 << " " << ans[i] + 1 << "\n";
    }
    return 0;
}

Python 範例程式碼

import queue

m, n = map(int, input().split())
sch = [{} for _ in range(m)] # school data
acceptCnt = [0]*m
for i in range(m):
    ins = list(map(int, input().split()))
    acceptCnt[i] = ins[0]
    for j in range(2, len(ins)):
        sch[i][ins[j]-1] = j-2
stu = [list(map(int, input().split())) for _ in range(n)] # student data
for i in stu:
    for j in range(1, i[0]+1):
        i[j] -= 1 # convert to 0-based index
res = [-2]*n # the school that the student will go to
tried = [0]*n # the number of schools tried for this student
nowAcc = [[] for _ in range(m)] # the students that have accepted this school
q = queue.Queue()
for i in range(n):
    q.put(i)
while not q.empty():
    now = q.get()
    tried[now] += 1
    if tried[now] >= len(stu[now]): continue # no more school to try
    toTry = stu[now][tried[now]]
    if now not in sch[toTry]:
        q.put(now)
        continue # the school doesn't know this student
    if len(nowAcc[toTry]) < acceptCnt[toTry]: # not full yet
        res[now] = toTry
        nowAcc[toTry].append(now)
    else:
        toPut = now
        for i in range(acceptCnt[toTry]):
            if sch[toTry][nowAcc[toTry][i]] > sch[toTry][toPut]: # better student
                res[toPut] = toTry
                toPut, nowAcc[toTry][i] = nowAcc[toTry][i], toPut
        res[toPut] = -2
        q.put(toPut)
for i in range(n): print(f"{i+1} {res[i]+1}")