Crossing River POJ - 1700 (经典题)

题目

A group of N people wishes to go across a river with only one boat, which can at most carry two persons. Therefore some sort of shuttle arrangement must be arranged in order to row the boat back and forth so that all people may cross. Each person has a different rowing speed; the speed of a couple is determined by the speed of the slower one. Your job is to determine a strategy that minimizes the time for these people to get across.

Input
The first line of the input contains a single integer T (1 <= T <= 20), the number of test cases. Then T cases follow. The first line of each case contains N, and the second line contains N integers giving the time for each people to cross the river. Each case is preceded by a blank line. There won’t be more than 1000 people and nobody takes more than 100 seconds to cross.
Output
For each test case, print a line containing the total number of seconds required for all the N people to cross the river.
Sample Input

1
2
3
1
4
1 2 5 10

Sample Output

1
17

思路

刚开始看到这题时,脑海里首先想到的是让速度最快的的人一趟趟地来回接送,这样就可以使得回来的时间最少,从而总时间最少。然而,却发现这种方法连样列都过不了,那么这种方法肯定是有问题。
接着忽然想到,如果先把最快和次快的先运过去,让最快的回来,再让最慢和次慢的过去,让次快的回来,这样子,就把最慢和次慢的运过去,其中运最慢和次慢的时间为{最慢},而不是像第一段中的为{最慢+次慢}。
再一次写好,交上去,WA。
。。。
又想到,这不是贪心吗!贪心肯定是每次着眼于当前最有利的吗?明白了。
1、最快和最慢运过去,最快回来;再,最快和次慢过去,最快回来。
2、最快和次快运过去,最快回来;再,最慢和次慢过去,次快回来。
这两种方案都可以把最慢和次慢运过去,即取两者所花时间最少方案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN=1e6;
int n;
int arr[MAXN];

bool cmp(int a,int b) {
return a<b;
}
int main() {

// freopen("in.txt","r",stdin);
int Case;
cin>>Case;
while(Case--) {
cin>>n;
for(int i=1;i<=n;i++)
cin>>arr[i];

sort(arr+1,arr+n+1,cmp);
int ans=0;
int i;
for(i=n;i>3;i-=2) {
int MIN=min(arr[i]+arr[i-1]+2*arr[1],arr[1]+2*arr[2]+arr[i]);
ans+=MIN;
}
if(i==3)
ans+=arr[1]+arr[2]+arr[3];
else if(i==2)
ans+=arr[2];
else ans+=arr[1];
cout<<ans<<endl;
}
return 0;
}
-------------本文结束感谢您的阅读-------------
0%