問題：

過河問題

時間限制：1000?ms ?|? 內(nèi)存限制：65535?KB 難度：5 描述

在漆黑的夜里，N位旅行者來到了一座狹窄而且沒有護欄的橋邊。如果不借助手電筒的話，大家是無論如何也不敢過橋去的。不幸的是，N個人一共只帶了一只手電筒，而橋窄得只夠讓兩個人同時過。如果各自單獨過橋的話，N人所需要的時間已知；而如果兩人同時過橋，所需要的時間就是走得比較慢的那個人單獨行動時所需的時間。問題是，如何設(shè)計一個方案，讓這N人盡快過橋。?

輸入

第一行是一個整數(shù)T(1<=T<=20)表示測試數(shù)據(jù)的組數(shù)
每組測試數(shù)據(jù)的第一行是一個整數(shù)N(1<=N<=1000)表示共有N個人要過河
每組測試數(shù)據(jù)的第二行是N個整數(shù)Si,表示此人過河所需要花時間。(0<Si<=100)

輸出

輸出所有人都過河需要用的最少時間

樣例輸入

1 4 1 2 5 10

樣例輸出

17

分析：

當(dāng)只有一個人時：時間s=a[0];

當(dāng)人數(shù)為二：時間s=a[1];

當(dāng)人數(shù)為三：時間s=a[0]+a[1]+a[2];

當(dāng)人數(shù)為四：時間s=a[0]+a[2]>2*a[1] ? a[0]+3*a[1]+a[3] : 2*a[0]+a[1]+a[2]+a[3];（如：一：1,2,5,10；二：1,7,8,10）

我的代碼：

#include <stdio.h> #include <algorithm> using namespace std; int main() {int t;scanf("%d", &t);while(t--){int n, a[1005]={0};scanf("%d", &n);for(int i=0; i<n; i++){scanf("%d", &a[i]);}sort(a, a+n);if(n==1) printf("%d\n", a[0]);else if(n==2) printf("%d\n", a[1]);else if(n==3) printf("%d\n", a[0]+a[1]+a[2]);else if(n==4) printf("%d\n", 2*a[1]<a[0]+a[2] ? a[0]+3*a[1]+a[3] : 2*a[0]+a[1]+a[2]+a[3]);else {int s=0;for(int i=n-1; i>1; i-=2){if(i-1==2)//只剩4個人，所有人都過去{s += 2*a[1]<a[0]+a[i-1] ? a[0]+3*a[1]+a[i] : 2*a[0]+a[1]+a[i-1]+a[i];break;}if(i-1==1)//只剩3個人，所有人都過去{s += a[0]+a[1]+a[i];break;}/*此時剩余人數(shù)大于4，只需要通過最快的兩個人（或一個人）把最后兩個人送到對岸，然后自己返回接剩下的人*/ s += 2*a[1]<a[0]+a[i-1] ? a[0]+2*a[1]+a[i] : 2*a[0]+a[i-1]+a[i];}printf("%d\n", s);}}return 0; }

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的贪心算法之——过河问题（nyoj47）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。