现在的位置: 首页 > 综合 > 正文

NYOJ 47 过河问题

2018年01月21日 ⁄ 综合 ⁄ 共 1093字 ⁄ 字号 评论关闭

过河问题

时间限制:1000 ms  |  内存限制:65535 KB
难度:5
描述

在漆黑的夜里,N位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话,大家是无论如何也不敢过桥去的。不幸的是,N个人一共只带了一只手电筒,而桥窄得只够让两个人同时过。如果各自单独过桥的话,N人所需要的时间已知;而如果两人同时过桥,所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是,如何设计一个方案,让这N人尽快过桥。 

输入
第一行是一个整数T(1<=T<=20)表示测试数据的组数
每组测试数据的第一行是一个整数N(1<=N<=1000)表示共有N个人要过河
每组测试数据的第二行是N个整数Si,表示此人过河所需要花时间。(0<Si<=100)
输出
输出所有人都过河需要用的最少时间
样例输入
1
4
1 2 5 10
样例输出
17
来源
/*题解:
每次过两个人,要考虑2种情况:
第一种:a[0],a[1]过,a[0]回来(递手电筒);a[n-1],a[n-2]过,a[1]回来。
耗时:a[1]+a[0]+a[n-1]+a[1] = a[0]+2*a[1]+a[n-1]; 
第二种:a[0],a[n-1]过,a[0]回来;a[0],a[n-2]过,a[0]回来。 
耗时:a[n-1]+a[0]+a[n-2]+a[0] = 2*a[0]+a[n-1]+a[n-2];
从上面可以看出,每次a[0],a[1]都要回来,改变的只是a[n-1]、a[n-2].
最后有剩余2、3个人,两种情况。由于初始化sum = a[1],故剩余2人的可以直接输出。
剩余三人的sum += a[0]+a[2];
*/ 
代码如下: 
#include<cstdio>
#include<algorithm>
using namespace std; 
int main()
{
	int T,i,n,m,a[1010],sum;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(i=0; i<n; i++)
		{
			scanf("%d",&a[i]);
		}
		if(n==1) //就一个人,直接输出 
		{
			printf("%d\n",a[0]);
			continue;
		}
		sort(a,a+n);
		sum = a[1]; //sum初始为a[1]. 
		while(n>3)
		{
			if(a[0]+2*a[1]+a[n-1]>2*a[0]+a[n-1]+a[n-2])
				sum += 2*a[0]+a[n-1]+a[n-2];
			else sum += a[0]+2*a[1]+a[n-1];
			n -= 2;
		}
		if(n==3) sum += a[0]+a[n-1];
		printf("%d\n",sum);
	}
	return 0;
}

抱歉!评论已关闭.