天天看點

監考安排 --- 簡單的貪心政策

說到監考安排,最大的限制規則有倆,一個是每個老師盡量監考自己執教的科目,一個是每個老師的監考盡量安排在一天。

那麼這裡我們可以用到簡單的貪心政策來得出解,注意,這裡是得出一個方案,不一定是最優方案,因為限制條件不多,是以本身不存在最優方案一說(最優方案指交換任意其中的兩場考試的監考安排,都會達不到要求)。

那麼接下來我們介紹一下監考的政策。

首先是所需要的變量值和接口:

監考人員數量為n,監考總科目數為m。顯然每個人所需要監考的場次數量最多為Max = (m - 1) / n + 1,首先我們先給每個監考人員和科目編号。

(1) map<string, int> member. ---監考人員編号

(2) map<string, int> subject. ---監考科目編号

接下來我們需要根據剛剛編号建立一些值:

(3) list<int> num. ---每個監考人員目前監考場次的數量

(4) list<list<int> > sub_mem ---每門科目所對應的所有監考人員

(5) list<list<int> > arrangement1---考試的安排

(6) list<list<int> > arrangement2---監考的安排(也就是我們需要得到的結果)

(7) queue<int> q ---目前時間下已經參與監考了的人的編号。

建立好之後,我們就可以開始進行安排:

首先我們先周遊考試安排表:

每周遊到一個科目,我們就去周遊sub_mem和q,看是否能找到同一個數,如果找不到,那我們就直接周遊sub_mem找到第一個次數小于Max的,插入arrangement2.get(i).get(j),中num+1後,将其加入到q到。如果這裡再遇到找不到,那麼我們就直接從q中進行尋找,進行同樣的操作。

每周遊一天,我們就将q進行清空:

while(!q.empty()) {
  q.pop();
}