OI——过河Crossing River(豪神的题)

封面女神:Joyce Jonathan, 法国著名民谣女歌手,代表作《Ça Ira》

openjudge上面的贪心算法里面有一道过河的问题,假期里豪神领我们做过,当时还是苯宝宝做出来的//小骄傲。

题面如下

总时间限制:
1000ms
内存限制:
65536kB
描述
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.
输入
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. There won’t be more than 1000 people and nobody takes more than 100 seconds to cross.
输出
For each test case, print a line containing the total number of seconds required for all the N people to cross the river.
样例输入
1
4
1 2 5 10
样例输出
17

好了其实就是我们通过实践会发现运输的方法有两种第一种方法时间为b*2+a+d; 第二种方法时间为c+d+2*a,那么只需要检查哪个时间更短即可。

以下代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX=1006;
int n,Pe[MAX];
int main() {
	int t;
	scanf("%d",&t);
	while(t--) {
		scanf("%d",&n);
		for( int i=1; i<=n; ++i )
			scanf("%d",&Pe[i]);
		sort(Pe,Pe+n+1);
		int sum=0;
		while( n ) {
			if( n==1 ) {
				sum+=Pe[1];
				break;
			} else if( n==2 ) {
				sum+=Pe[2];
				break;
			} else if( n==3 ) {
				sum+=Pe[3]+Pe[1]+Pe[2];
				break;
			} else {
				if( 2*Pe[2]>Pe[1]+Pe[n-1] )
					sum+=2*Pe[1]+Pe[n-1]+Pe[n];
				else
					sum+=2*Pe[2]+Pe[1]+Pe[n];
				n-=2;
			}
		}
		printf("%d\n",sum);
	}
	return 0;
}

求打赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注