題目： 過河問題 時間限制：1000 ms | 內存限制：65535 KB 難度：5 描述 在漆黑的夜里，N位旅行者來到了一座狹窄而且沒有護欄的橋邊。如果不借助手電筒的話，大家是無論如何也不敢過橋去的。不幸的是，N個人一共只帶了一只手電筒，而橋窄得只夠讓兩個人同時過。如果各自單獨過橋的話，N人所需要的時間已知；而如果兩人同時過橋，所需要的時間就是走得比較慢的那個人單獨行動時所需的時間。問題是，如何設計一個方案，讓這N人盡快過橋。
輸入 第一行是一個整數T(1<=T<=20)表示測試數據的組數 每組測試數據的第一行是一個整數N(1<=N<=1000)表示共有N個人要過河 每組測試數據的第二行是N個整數Si,表示此人過河所需要花時間。(0
#include<stdio.h> #include<algorithm> using namespace std; int main() { int t; int a[1005]; scanf("%d",&t); while(t--) { int sum=0; int n; scanf("%d",&n); for(int i=0; i<n; i++) scanf("%d",&a[i]); sort(a,a+n); while(n>=4) { if(2*a[1]+a[0]+a[n-1]<a[n-1]+a[n-2]+2*a[0]) sum+=2*a[1]+a[0]+a[n-1]; else sum+=a[n-1]+a[n-2]+2*a[0]; n-=2; } if(n==1) sum+=a[0]; else if(n==2) sum+=a[1]; else if(n==3) sum+=a[1]+a[0]+a[2]; 示例代碼：#include<stdio.h> #include<algorithm> using namespace std; int a[1005]; int main() { int T, n, i; scanf("%d",&T); while(T--) { scanf("%d",&n); for(i = 0; i < n; i++) scanf("%d",&a[i]); sort(a,a+n); int sum = 0; while(n >= 4) { if((a[1] * 2 + a[n-1] + a[0]) > (2 * a[0] + a[n-1] + a[n-2])) { //求出最長的兩個人過橋所用的最短時間 sum += a[n-1]; //用時最短的和用時最長的一起過去 sum += a[0]; //用時最短的回來 sum += a[n-2]; //用時最短的和用時第二長的一起過去 sum += a[0]; //用時最短的回來 } else { sum += a[1]; //最短的和第二短的一起過去 sum += a[0]; //最短的回來 sum += a[n-1]; //最長的和第二長的一起過去 sum += a[1]; //第二短的回來 } n -= 2; } if(n == 3) sum += a[1] + a[0] + a[2]; else if(n == 2) sum += a[1]; else sum += a[0]; printf("%d/n",sum); } return 0; }新聞熱點
疑難解答
