2013年7月18日 星期四

234 - Switching Channels

 Switching Channels 

CPN (The Couch Potato Network) 擁有許多有線頻道,他們要安排節目的時間,好讓觀眾不會錯過節目,為了做到這一點,發們發現有一個 對齊點 (alignment point) 相當重要,理想的情況時,每個對齊點恰好是一個心的節目開始,而有些對齊點又特別重要,例如晚間新聞的時間點就相當重要。當觀眾知道節目表後,他們可能會少看一些 CPN 節目!因為可能會少看到節目的一部分,或者是要等待上一個節目結束,而這段時間稱為 miss time。而你被雇用來找到一個最恰當的節目安排方式。

miss time 的定義為對齊點與最鄰近的節目開始或節目結束差的絕對值,而 total miss time 則是在相同重要程度的對齊點的 miss time 總和。一個節目安排方式優於另一個節目的安排方式,是先比較最重要的 total miss time,再比較次重要的 total miss time ... 類推。

Input

每組測資會有一個整數 p (0 <= p <= 8),表示節目的個數。
每組測資的時間點從 0 開始,接下來則會有 p 個整數表示節目的長度(單位為分鐘)。

接下來會有一個整數表示對齊點的個數 a (0 <= a <= 8),每組對齊點有兩個整數 i, t
(1 <= i <= 5),i 表示重要程度,1 表示最重要,2 表示第二重要 ... 類推。而 t 則表示對齊的時間點,且不會有兩個對齊點具有相同的 t

Output

對於每組測資,輸出一行測資組編號,格式如下:

Data set n
接著輸出最佳的節目編排方式, 以及輸出所有的 total miss time 的總和。
如果有多組最佳的節目編排方式,則任何一組都可以。

Sample Input

4  30 45 45 15
3  1 60  2 90  3 15
6  10 15 13 18 25 33
4  1 30  2 15  2 45  1 60
0

Sample Output

Data set 1
Order: 15 45 30 45 
Error: 0
Data set 2
Order: 15 13 33 25 18 10
Error: 19

範例輸入解釋

Data set 2
Order: 15 13 33 25 18 10
Error: 19
得到節目的時間點為 0, 15, 28, 61, 86, 104, 114。
對於最重要的時間點 30, 60
30 最鄰近的時間為 28,miss time = |30-28| = 2
60 最鄰近的時間為 61,miss time = |60-61| = 1
total miss time = 2+1 = 3
對於次重要的時間點為 15, 45
15 最鄰近的時間為 15,miss time = |15-15| = 0
45 最鄰近的時間為 61,miss time = |45-61| = 16
total miss time = 0+16 = 16
=> Error = 3+16 = 19