NPSC補完計劃

登入註冊帳號.

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

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2005高中組決賽
 NPSC 2005 高中組 決賽 A.誰先晚餐

作者 主題: NPSC 2005 高中組 決賽 A.誰先晚餐  (閱讀 3076 次)

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 242
    • 檢視個人資料
NPSC 2005 高中組 決賽 A.誰先晚餐
« 於: 十二月 08, 2009, 02:33:31 pm »

NPSC 2005 高中組 決賽 A.誰先晚餐

說明:有一群人要進同一家店吃晚餐,每個人點的餐烹煮的時間都不一樣,而每個人吃完時間也不一樣。而店家一次只能煮一道菜,請問要如何烹煮,才能最早讓所有人都吃完離開。

解法:使用貪婪演算法,讓吃得越久的人越早吃,這樣所有人就可以越早離開。

參考程式:(By sagit)

代碼: [選擇]
// NPSC 2005 決賽 - 題目 A - 誰先晚餐 //
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstdlib>
#define MAX 10000

using namespace std;

int cook[MAX], eat[MAX], n;

void SortByEat()
{
    int i, j, m;
    for (i=0; i<n-1; i++)
    {
        for (j=i+1, m=i; j<n; j++)
            if (eat[j]>eat[m]) m=j;
        if (m!=i)
        {
            swap(eat[i], eat[m]);
            swap(cook[i], cook[m]);
        }
    }
}

int main()
{
    ifstream fin("pa.in");
    ofstream fout("pa.out");
    int i, cook_time, leave_time, max;
   
    while (1)
    {
        fin >> n;
        if (n==0) break;
        for (i=0; i<n; i++)
            fin >> cook[i] >> eat[i];
        SortByEat();
        for (i=0, max=0, cook_time=0; i<n; i++)
        {
            cook_time+=cook[i];
            leave_time=cook_time+eat[i];
            if (leave_time>max) max=leave_time;
        }
        fout << max << endl;
    }
   
//    system("PAUSE");
    return 0;
}
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2005高中組決賽
 NPSC 2005 高中組 決賽 A.誰先晚餐