POJ1700 (Crossing River)[贪心]

发表于 | 更新于 | | 阅读次数：

题目链接：http://poj.org/problem?id=1700

思路引用自https://blog.csdn.net/u014492609/article/details/40918435

当n=1,2,3时所需要的最小时间很容易求得,现在由n>=4,假设n个人单独过河所需要的时间存储在数组t中,将数组t按升序排序,那么 这时将单独过河所需要时间最多的两个旅行者送到对岸去,有两种方式:

  1. 最快的(即所用时间t[0])和次快的过河,然后最快的将船划回来,再次慢的和最慢的过河,然后次快的将船划回来。即所需时间为:t[0]+2*t[1]+t[n-1]
  2. 最快的和最慢的过河,然后最快的将船划回来,再最快的和次慢的过河,然后最快的将船划回来,即所需时间为:2*t[0]+t[n-2]+t[n-1]

注意这两种过河方式是两种最优的过河方式，每一次过河都应该判断具体采用哪一种。

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=1009;
int n;
int a[maxn];
int main() {
	int T,f,s;
	int r;
	ll ans=0;
	scanf("%d",&T);
	while(T--) {
		ans=0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++) {
			scanf("%d",a+i);
		}
		if(n==1) {
			printf("%d\n",a[1]);
		}
		else if(n==2) {
			printf("%d\n",max(a[1],a[2]));
		}
		else if(n==3) {
			printf("%d\n",a[1]+a[2]+a[3]);
		}
		else if(n&1) {
			sort(a+1,a+n+1);
			f=a[1];
			s=a[2];
			r=n;
			while(r>3) {
				ans+=min(s+f+a[r]+s,a[r]+f+a[r-1]+f);
				r-=2;
			}
			ans+=a[1]+a[2]+a[3];
			printf("%lld\n",ans);
		}
		else {
			sort(a+1,a+n+1);
			f=a[1];
			s=a[2];
			r=n;
			while(r>2) {
				ans+=min(s+f+a[r]+s,a[r]+f+a[r-1]+f);
				r-=2;
			}
			ans+=s;
			printf("%lld\n",ans);
		}
	}
}