題目： 過(guò)河問(wèn)題 時(shí)間限制：1000 ms | 內(nèi)存限制：65535 KB 難度：5 描述 在漆黑的夜里，N位旅行者來(lái)到了一座狹窄而且沒(méi)有護(hù)欄的橋邊。如果不借助手電筒的話，大家是無(wú)論如何也不敢過(guò)橋去的。不幸的是，N個(gè)人一共只帶了一只手電筒，而橋窄得只夠讓兩個(gè)人同時(shí)過(guò)。如果各自單獨(dú)過(guò)橋的話，N人所需要的時(shí)間已知；而如果兩人同時(shí)過(guò)橋，所需要的時(shí)間就是走得比較慢的那個(gè)人單獨(dú)行動(dòng)時(shí)所需的時(shí)間。問(wèn)題是，如何設(shè)計(jì)一個(gè)方案，讓這N人盡快過(guò)橋。
輸入 第一行是一個(gè)整數(shù)T(1<=T<=20)表示測(cè)試數(shù)據(jù)的組數(shù) 每組測(cè)試數(shù)據(jù)的第一行是一個(gè)整數(shù)N(1<=N<=1000)表示共有N個(gè)人要過(guò)河 每組測(cè)試數(shù)據(jù)的第二行是N個(gè)整數(shù)Si,表示此人過(guò)河所需要花時(shí)間。(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])) { //求出最長(zhǎng)的兩個(gè)人過(guò)橋所用的最短時(shí)間 sum += a[n-1]; //用時(shí)最短的和用時(shí)最長(zhǎng)的一起過(guò)去 sum += a[0]; //用時(shí)最短的回來(lái) sum += a[n-2]; //用時(shí)最短的和用時(shí)第二長(zhǎng)的一起過(guò)去 sum += a[0]; //用時(shí)最短的回來(lái) } else { sum += a[1]; //最短的和第二短的一起過(guò)去 sum += a[0]; //最短的回來(lái) sum += a[n-1]; //最長(zhǎng)的和第二長(zhǎng)的一起過(guò)去 sum += a[1]; //第二短的回來(lái) } 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; }新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
