2011-08-27 10:59:32Morris
b180. 1. 遊園接駁車
b180. 1. 遊園接駁車
內容 ：
某一遊樂園分為水上樂園與探索樂園，旅客玩完水上樂園之後，接著便排隊搭乘單人客車進入探索樂園遊園。每部車只可搭載一名旅客進入探索樂園，旅客先到先搭車；如果某單人客車已經準備好要搭載旅客，但是此時並沒有等待中的旅客，那麼該輛車就必須等待。若旅客等待客車的時間超過 30 分鐘(包含30分鐘)就會放棄搭乘而離開園區。現在有一個由若干個旅客所組成的旅行團同時來到園區，請問在已知下列三個條件
(1) 該旅行團的旅客數量 (10<=m<=60)
(2) 該旅行團的個別旅客待在水上樂園的分鐘數 (1<=t<=60)
(3) 個別旅客環繞探索樂園的分鐘數 (1<=T<=60)
請撰寫程式計算至少需要幾部單人客車，才能滿足該旅行團所有的旅客，不讓旅客等超過30分鐘。 (m，t，T 皆為整數 ) 請輸出至少需要單人客車的數量 ?
輸入說明 ：
第一行為該旅行團人數，接下來每一行都有兩筆數據，第一筆代表個別旅客待在水上樂園的分鐘數，第二筆代表個別旅客環繞探索樂園的分鐘數。（輸入順序未必按照旅客待在水上樂園的分鐘數排列）
輸出說明 ：
至少需要單人客車的數量。
範例輸入 ：
115 3040 3035 515 1030 2010 4045 550 55 1035 550 30510 2020 3010 4510 5015 30
範例輸出 ：
23
提示 ：
出處 ：
/**********************************************************************************/
/* Problem: b180 "1. 遊園接駁車" from 97高市資訊學科能力競賽 */
/* Language: C */
/* Result: AC (2ms, 216KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-27 10:52:27 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define oo 2147483647
typedef struct {
int wait, time;
}D;
D Cust[61], X[61];
void Merge(int l, int m, int r) {
int In1 = l, In2 = m+1;
int a, b, Top = 0;
while(In1 <= m && In2 <= r)
if(Cust[In1].wait < Cust[In2].wait ||
(Cust[In1].wait == Cust[In2].wait && Cust[In1].time < Cust[In2].time))
X[Top++] = Cust[In1++];
else
X[Top++] = Cust[In2++];
while(In1 <= m) X[Top++] = Cust[In1++];
while(In2 <= r) X[Top++] = Cust[In2++];
for(a = 0, b = l; a < Top; a++, b++)
Cust[b] = X[a];
}
void MergeSort(int l, int r) {
if(l < r) {
int m = (l+r)/2;
MergeSort(l, m);
MergeSort(m+1, r);
Merge(l, m, r);
}
}
int n, a, Ans, bike[61] = {};
void DFS(int now, int time) {
if(now == n) {
if(time < Ans)
Ans = time;
return;
}
if(time >= Ans) return;
int a, t;
for(a = 0; a <= time; a++) {
if(bike[a] < Cust[now].wait+30) {
t = bike[a];
if(bike[a] >= Cust[now].wait)
bike[a] = bike[a] + Cust[now].time;
else
bike[a] = Cust[now].wait + Cust[now].time;
DFS(now+1, time);
bike[a] = t;
}
}
bike[time+1] = Cust[now].time + Cust[now].wait;
DFS(now+1, time+1);
}
main() {
while(scanf("%d", &n) == 1) {
for(a = 0; a < n; a++)
scanf("%d %d", &Cust[a].wait, &Cust[a].time);
MergeSort(0, n-1);
Ans = oo, DFS(0, -1);
printf("%d\n", Ans+1);
}
return 0;
}
下一篇：d370. 2. 盤中飧