本文主要是介绍南工ACM:过河问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
描述
在漆黑的夜里,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
其他测试样例:
5
1 4 7 6 9
29
6
1 4 7 8 10 12
42
4
1 7 8 9
26
5
1 7 8 9 10
37
思想:
由于只有一个手电筒,那么两个人过河后,必须还要有一个人把手电筒送回来,这个时间也要计算进去。
令a[i]表示第i个人需要的时间(i=1~n)。先将a[i]用快排法从小到大排序。
当n==1时,需要时间sum=a[1]
当n==2时,需要时间sum=a2
当n==3时,需要时间sum=a[1]+a[2]+a[3]
当n>=4时,我们总共有两种送人的方式。
第一种方式:
第二种方式:
我们可以发现,当n>=4时,只有这两种方式。为什么?
从上图可以得知,当n>=4时,不管n为多大,我们每次变动的都只是最左边的a[1],a[2] ; 和最右边的a[n],a[n-1]。与中间的元素都无关。变动一次后,就能够将两个a吊到河对岸。问题就由a[1~n]就变了a[1~(n-2)],这之间的消耗时间也是最小的。
思想就是,每次尽可能的让最大值和次大值一起出去,然后让之前调入的小值下来,这样以后就不用调次大值,从而减少了开销。但是这前提是,必须要有“之前调入的小值”。为了减少开销这个值尽可能的小,所以构建这个已经调入的小值得方式就是:a1,a2调过去,再把a1调回来。但是这又增大了一些开销a2+a1。而方式2的开销就是调a[n]时要浪费一个a[1],调a[n-1]时又要用一个a[1],同时还要消耗a[n-1],而方式一是不消耗a[n-1]的。所以我们就要比较方式一和方式二,在什么情况下选择方式一,在什么情况下选方式二。
方式一:调成上图的恒等不变式所需开销为:a[2]+a[1]+a[n]+a[2]
方式二:调成上图的恒等不变式所需开销为:a[n]+a[1]+a[n-1]+a[1]
(a[2]+a[1]+a[n]+a[2] ) - (a[n]+a[1]+a[n-1]+a[1])=(a[2]+a[2]) - (a[n-1] + a[1] )
所以如果 (a[2]+a[2]) 》(a[n-1] + a[1] ) 选方式二,如果 (a[2]+a[2]) 《 (a[n-1] + a[1] ) 选方式一
然后用对应的方式计算一次开销后,再n=n-2 继续循环用这个方法,直到n<=3.
#include<stdio.h>
#include<malloc.h>void kuaipai(int* a,int l,int r);
int main()
{int m=0,n=0;int i=1,j=1;int* a=0;int b=0;int sum=0;scanf("%d",&m);for(i=1;i<=m;i++){scanf("%d",&n);a=(int*)malloc(sizeof(int)*(n+1));for(j=1;j<=n;j++){scanf("%d",a+j);}kuaipai(a,1,n);sum=0;while(n>=0){if(n==1){printf("%d\n",sum+a[1]);break;}if(n==2){printf("%d\n",sum+a[2]);break;}if(n==3){printf("%d\n",sum+a[1]+a[2]+a[3]);break;}if(a[2]+a[2] < a[n-1]+a[1]){sum=sum+a[2]+a[1]+a[n]+a[2];n=n-2;}else{sum=sum+a[n]+a[1]+a[n-1]+a[1];n=n-2;}}}return 0;
}void kuaipai(int* a,int l,int r)
{int i=l,j=l;int x=a[r];int y=0;if(l>=r)return;for(i=l;i<=r-1;i++){if(a[i]<x){y=a[i];a[i]=a[j];a[j]=y;j++;}}y=a[j];a[j]=a[r];a[r]=y;kuaipai(a,l,j-1);kuaipai(a,j+1,r);
}
这篇关于南工ACM:过河问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!