NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2004高中組初賽
 NPSC 2004 高中組 初賽 D.工作排程

作者 主題: NPSC 2004 高中組 初賽 D.工作排程  (閱讀 1468 次)

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 238
    • 檢視個人資料
NPSC 2004 高中組 初賽 D.工作排程
« 於: 十二月 08, 2009, 03:36:48 pm »

NPSC 2004 高中組 初賽 D.工作排程

說明:給你一連串工作的處理時間和截止時間,問你是否可以讓每個工作都如期完成。

解法:先將所有工作依照截止時間排序,截止時間越早的要越先完成,用一個迴圈去計算累計的處理時間,如果超過截止時間,則無法如期完成,反之則是可以如期完成。

參考程式:(By sagit)

代碼: [選擇]
// NPSC 2004 初賽 - 題目 D - 工作排程 //
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <algorithm>
#define MAX 1000

using namespace std;

int m, e[MAX], d[MAX];

int Check()
{
    int i, j, k;
    for (i=0; i<m-1; i++)
    {
        for (j=i+1, k=i; j<m; j++)
            if ( d[j]<d[k] ) k=j;
        swap(e[i], e[k]);
        swap(d[i], d[k]);
    }
    for (i=0, k=0; i<m; i++)
    {
        k+=e[i];
        if ( k>d[i] ) return 0;
    }
    return 1;
}

int main()
{
    ifstream fin("pd.in");
    ofstream fout("pd.out");
    int n, i, j;

    fin >> n;
    for (i=0; i<n; i++)
    {
        fin >> m;
        for (j=0; j<m; j++)
            fin >> e[j] >> d[j];
        if ( Check() ) fout << "schedulable" << endl;
        else fout << "unschedulable" << endl;
    }

//    system("PAUSE");
    return 0;
}
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2004高中組初賽
 NPSC 2004 高中組 初賽 D.工作排程