HYSBZ 1216 [HNOI2003]作業系統

題目連結

1216: [HNOI2003]作業系統
Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 1045  Solved: 565
[Submit][Status][Discuss]
Description

寫一個程式來模拟作業系統的程序排程。假設該系統隻有一個CPU，每一個程序的到達時間，執行時間和運作優先級都是已知的。其中運作優先級用自然數表示，數字越大，則優先級越高。如果一個程序到達的時候CPU是空閑的，則它會一直占用CPU直到該程序結束。除非在這個過程中，有一個比它優先級高的程序要運作。在這種情況下，這個新的（優先級更高的）程序會占用CPU，而老的隻有等待。如果一個程序到達時，CPU正在處理一個比它優先級高或優先級相同的程序，則這個（新到達的）程序必須等待。一旦CPU空閑，如果此時有程序在等待，則選擇優先級最高的先運作。如果有多個優先級最高的程序，則選擇到達時間最早的。
Input

輸入檔案包含若幹行，每一行有四個自然數（均不超過108），分别是程序号，到達時間，執行時間和優先級。不同程序有不同的編号，不會有兩個相同優先級的程序同時到達。輸入資料已經按到達時間從小到大排序。輸入資料保證在任何時候，等待隊列中的程序不超過15000個。
Output

按照程序結束的時間輸出每個程序的程序号和結束時間
Sample Input
1 1 5 3

2 10 5 1

3 12 7 2

4 20 2 3

5 21 9 4

6 22 2 4

7 23 5 2

8 24 2 4
Sample Output
1 6

3 19

5 30

6 32

8 34

4 35

7 40

2 42
           

這題利用了優先隊列

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

#define iinf 0x7FFFFFFF

// AC
// 優先隊列

using namespace std;

int proCount;

struct Pro {
    int id;
    int comeTime;
    int runTime;
    int priority;
    Pro(int a, int b, int c, int d): id(a), comeTime(b), runTime(c), priority(d) {}
};

struct cmp {//判斷“一個元素是否小于另一個元素”的結構體
// 重載operator ()必須是某個類的成員函數。
// 當某個類重載了()方法，這個類就可以成為函數對象。
    bool operator() (Pro*& p0, Pro*& p1) const {//關于這裡的參數最前是否需要加const關鍵字，我的應對政策是：先試着加上，如果有錯的話，編譯器會回答找不到對應的方法，比如，加了const提示 ： error: no match for call to ‘(cmp) (Pro*&, Pro*&)’，可知這裡不用加const
        if (p0->priority == p1->priority) {//若優先級相同，則更早來的在前面（優先隊列中最前的元素，即top()，是比較之後值最大的那個元素，要讓時間更前的元素排得越前，則它在這個自定義比較函數裡面的“值”越大越好，即：優先級相同的兩個元素，時間更前的元素反而更大）
            return p0->comeTime > p1->comeTime;//若第一個參數指向的元素來到時間比第二個元素的早，則表達式傳回 false，代表第一個參數指向的元素大于第二個元素，排的更前。
        } else {
            return p0->priority < p1->priority;//若優先級不同，則優先級高的在前面
        }
    }
};

/**
*   為什麼我不直接在Pro結構體内部重載 < 操作符，因為我這個queue存的是指針變量，并不是實際的元素，重載Pro結構體的 < 操作符不會有作用，因為這時候queue裡面比較的是Pro*類型的元素，我們要想辦法為Pro*類型的元素适配比較函數
*   是以我寫了上面那個比較函數，後來看了别人的代碼發現，上面這個自定義的比較函數其實可以不用這麼麻煩
*   我們要想辦法讓 < 操作符支援 Pro* 類型和 Pro* 類型之間的比較，是以我們可以在全局方範圍内重載 < 操作符
*   例如：
*   
*   bool operator < (Pro p0, Pro*& p1) {
*       if (p0->priority == p1->priority) {
*           return p0->comeTime > p1->comeTime;
*       } else {
*           return p0->priority < p1->priority;
*       }
*   }
*   同時下面的waitQu改成
*   priority_queue <Pro*> waitQu;
*   可是，編譯報錯
*    error: ‘bool operator<(Pro*&, Pro*&)’ must have an argument of class or enumerated type
*    bool operator < (Pro*& p0, Pro*& p1) {
*                                       ^
*   原來c++有些操作符在某些情況下是不能重載的，比如對兩個指針的比較的小于号操作符，這個操作符已經有具體實作了，我們不能重載它，否則那些庫裡面用到用<比較指針的操作都變成了我們自定義的操作了，豈不是亂了套
*/

queue<Pro*> allPro;

priority_queue <Pro*, vector<Pro*>, cmp> waitQu; //存放排隊等候中的程序
//                                  ^這裡在模闆中傳入比較函數的類型，相當于自己實作一個 < 函數

int main(int argc, char const *argv[])
{
    int a, b, c, d;
    Pro* t;
    while (~scanf("%d%d%d%d", &a, &b, &c, &d)) {
        t = new Pro(a, b, c, d);//這裡是手動在堆上申請記憶體，讓queue和priority_queue維護指針，實際上不用這樣，可以直接在棧上建立一個Pro元素，queue和priority_queue會進行拷貝操作，在堆上形成一份原來棧記憶體上的元素的拷貝
        allPro.push(t);//先讀取放到allPro這個隊列中
    }

    int nowTime = ;
    int stepTime;//一次步進多長時間

    for (; (!waitQu.empty()) || (!allPro.empty());) {//當等待隊列waitQu和allPro隊列都為空時就退出

        stepTime = iinf;

        if (!waitQu.empty()) { //若等待隊列中還有元素
            stepTime = min(stepTime, waitQu.top()->runTime);
        }

        if (!allPro.empty()) {//若未加入的任務隊列中還有元素
            stepTime = min(stepTime, allPro.front()->comeTime - nowTime);
        }
        //至此步進時長确定完成

        nowTime += stepTime;

        if (!waitQu.empty()) {
            //每次處理等待隊列中的第一個元素
            waitQu.top()->runTime -= stepTime;//等待隊列中的第一個元素的剩餘運作時間減去步進時間
            if (waitQu.top()->runTime == ) {//若任務執行完畢
                printf("%d %d\n", waitQu.top()->id, nowTime);
                delete waitQu.top();//記得釋放記憶體
                waitQu.pop();
            }
        }

        if (!allPro.empty()) {
            if (nowTime == allPro.front()->comeTime) {//若第一個未加入的任務時機已到，則加入任務到等待隊列中
                waitQu.push(allPro.front());
                allPro.pop();
            }
        }
    }

    return ;
}