当前位置: 首页 > 工具软件 > River Trail > 使用案例 >

Crossing River 【贪心】

东方淇
2023-12-01

https://vjudge.net/contest/285413#problem/B

题目大意:n个人过河,只有一条船,最多只能坐两个人,问最少用多长时间可以让所有人都过河,注意把船开过河还需要再开回来接人。

样例是1、2、5、10,想了很久最快都要18秒,但是答案是17,找了找答案,发现是这样n=滴

1、2先过,1回来,5,10再过,2回来,1、2最后过去,时间为2+1+10+2+2=17

过河有以下几种可能:

1.一人a过河,所用时间为a

2.两人a,b过河,a<b,所用时间为b

3.三人a,b,c过河,a<b<c,

      ①:a,c先过,所用时间为c

      ②:a返回,所用时间为a

      ③:a,b过桥,所用时间为b      时间总和为a+b+c

4.四人及以上过河,a<b<……<c<d

   方案一:由最快的a带c,d过桥:a带c过,a回来,a再带d过,a回来。所用时间为2*a+c+d,人数减少两个

   方案二:由最快的a和次快的b过河

       ①:a,b过河,所用时间为b

       ②:a返回  ,船给c,d,时间为a

       ③:c,d过河,所用时间为d,

       ④:b拿手电筒返回,时间为b       时间总和为a+2*b+d,人数减少两个

   当人数减少到<=3,就成了前三种情况
 

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int a[1005]; 
int main(){
	int t;
	cin>>t;
	while(t--){
		int n,result=0,m;
		cin>>n;
		for(int i=0;i<n;i++){
			cin>>a[i];
		}
		sort(a,a+n);
		m=n;
		while(m>=4){
			result+=min(2*a[0]+a[m-2]+a[m-1],a[0]+2*a[1]+a[m-1]);
			m-=2;   //人数减少两个,所以-2 
		}
		if(m==3){
			result+=a[0]+a[1]+a[2];
		} 
		else if(m==2){
			result+=a[1];
		}
		else if(m==1){
			result+=a[0];
		}
		cout<<result<<endl;
	}
	return 0;
}

 

 类似资料: