2011-05-29 07:43:17Morris
d872. 過橋問題
http://zerojudge.tw/ShowProblem?problemid=d872
內容 ：
/* Problem: d872 "過橋問題" from ACM簡易版 */
/* Language: C */
/* Result: AC (140ms, 232KB) on ZeroJudge */
/* Author: morris1028 at 2011-05-17 20:14:05 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
int Input() {
char cha;
unsigned int x = 0;
while(cha = getchar())
if(cha != ' ' && cha != '\n' || cha == EOF) break;
if(cha == EOF) return -1;
x = cha-48;
while(cha = getchar()) {
if(cha == ' ' || cha == '\n') break;
x = x*10 + cha-48;
}
return x;
}
int Line[1001] = {};
short Index1, Index2;
short Findback() {
while(1) {
if(Line[Index1]) {
Line[Index1] --;
return Index1;
}
else Index1--;
}
}
short Findnext() {
while(1) {
if(Line[Index2]) {
Line[Index2] --;
return Index2;
}
else Index2++;
}
}
main() {
register int N, a;
while(1) {
N = Input();
if(N == EOF) break;
for(a = 0, Index1 = 1000, Index2 = 0; a < N; a++)
Line[Input()]++;
register int time = 0;
register short t1, t2, Min1 = Findnext(), Min2 = Findnext(), Y, Z;
while(N > 3) {
Z = Findback(), Y = Findback();
t1 = Min2 + Min1 + Z + Min2;/*1. AB + A + YZ + B*/
t2 = Z + Min1 + Y + Min1;/*2. AZ + A + AY + A*/
time += (t1 < t2)? t1 : t2;
N -= 2;
}
if(N == 2) time += Min2;
else if(N == 3) time += Min1 + Min2 + Findnext();
else if(N == 1) time += Min1;
printf("%d\n", time);
}
return 0;
}
內容 ：
有n個人想要在晚上過橋，橋上每次最多只能容許2個人行走。由於全部只有一支手電筒，所以每次2個人拿著手電筒過橋後，必須有一人再把手電筒拿回來，這樣後面的人才能繼續過橋。
每個人走路的速度不同，過橋所需的時間也因此不同。而每次過橋的那2個人，其花費的時間以較慢的那個人計算（走的快的當然要等走的慢的，因為只有一支手電筒）。你的任務是寫一個程式，安排這n個人過橋，並使得總共花費的時間最少。
輸入說明
：
有多筆測試資料。每組測試資料的第一列有1個整數n，代表要過橋的人數（最多不會超過100000人）。接下來的n個整數，代表這n個人過橋所需的時間（秒），這些時間均不會超過1000秒。
輸出說明
：
每組測試資料輸出的第一列為一個整數，代表這n個人過橋所需的最少時間。
以第一組Sample Output為例說明：最少需17秒才能讓這4個人過橋。方式為：1秒、2秒的人先過橋，1秒的回來，5秒、10秒的過橋，2秒的回來，最後1秒、2秒的過橋，所以總共的時間為：2+1+10+2+2=17。
範例輸入 ：
4 1 2 5 10 4 1 98 99 100 5 1 3 6 8 12
範例輸出 ：
17 299 29
提示
：
這題過了之後就寫UVa ACM Q10037: Bridge吧
出處
：
ACM簡易版
(管理：david942j)
作法: greedy
分成兩種策略去做討論
1. AB + A + YZ + B
2. AZ + A + AY + A
選擇其一小的做
你可以很明顯的發現
不管哪一種作法第一快跟第二快的，總是會回到島的另一邊
來作為傳遞的人
應該說，一定會有人必須拿手電筒回來，那麼一定要找最快的回來
/**********************************************************************************/作法: greedy
分成兩種策略去做討論
1. AB + A + YZ + B
2. AZ + A + AY + A
選擇其一小的做
你可以很明顯的發現
不管哪一種作法第一快跟第二快的，總是會回到島的另一邊
來作為傳遞的人
應該說，一定會有人必須拿手電筒回來，那麼一定要找最快的回來
/* Problem: d872 "過橋問題" from ACM簡易版 */
/* Language: C */
/* Result: AC (140ms, 232KB) on ZeroJudge */
/* Author: morris1028 at 2011-05-17 20:14:05 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
int Input() {
char cha;
unsigned int x = 0;
while(cha = getchar())
if(cha != ' ' && cha != '\n' || cha == EOF) break;
if(cha == EOF) return -1;
x = cha-48;
while(cha = getchar()) {
if(cha == ' ' || cha == '\n') break;
x = x*10 + cha-48;
}
return x;
}
int Line[1001] = {};
short Index1, Index2;
short Findback() {
while(1) {
if(Line[Index1]) {
Line[Index1] --;
return Index1;
}
else Index1--;
}
}
short Findnext() {
while(1) {
if(Line[Index2]) {
Line[Index2] --;
return Index2;
}
else Index2++;
}
}
main() {
register int N, a;
while(1) {
N = Input();
if(N == EOF) break;
for(a = 0, Index1 = 1000, Index2 = 0; a < N; a++)
Line[Input()]++;
register int time = 0;
register short t1, t2, Min1 = Findnext(), Min2 = Findnext(), Y, Z;
while(N > 3) {
Z = Findback(), Y = Findback();
t1 = Min2 + Min1 + Z + Min2;/*1. AB + A + YZ + B*/
t2 = Z + Min1 + Y + Min1;/*2. AZ + A + AY + A*/
time += (t1 < t2)? t1 : t2;
N -= 2;
}
if(N == 2) time += Min2;
else if(N == 3) time += Min1 + Min2 + Findnext();
else if(N == 1) time += Min1;
printf("%d\n", time);
}
return 0;
}
下一篇：a048. 函数增减性
感謝大大><!!!
終於把這題給解決了!
小的目前還是高職生~
也只會寫vb QAQ!
看C有點痛苦...
但概念一樣就還好^^
3Q拉~