欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

poj1700快速渡河问题(贪心策略,详细解析)

程序员文章站 2022-03-26 16:52:23
...

二、快速渡河问题
翻译为中文
一队人(N个人)期望跨河,有一条船,一次只能载2个人,过河之后需要有一个人划回来,所有人才能够跨河,每个人划船速度都不同,两个人一组整体速度是由划船速度较慢的决定的。问题:确定一种策略用最少的时间所有人都能过河。


输入:
方案数:T(1<=T<=20)
人数:N<1000
速度:<100s
输出:
最少的时间
样例:
输入:
1
4
1 2 5 10
输出
17


分析思路:
有两种情况,
第一种:过河时间最少的人来回接送其他人;
第二种:过河时间最少和次少的人来回接送其他人;
4个人过河
首先4个人里面先选2个·,2个已过河的选1个再返回,剩下3个人里面选2个渡河,返回其中一个,最后2个人一起过河
poj1700快速渡河问题(贪心策略,详细解析)暴力解法:
4人过河
poj1700快速渡河问题(贪心策略,详细解析)看起来是DFS,一层一层,但是呢,会发现它的规模非常大,并且还有速度在里面,可以便于我们找到最优方案。
速度是1 2 5 10
两人一组由速度最慢的决定
poj1700快速渡河问题(贪心策略,详细解析)

  • 一般思路:

1.快的先走,回来快的(带一个慢的,快的去3次,返回2次);
2.只用最快的来回渡人
假设a,b,c,d依次递增
poj1700快速渡河问题(贪心策略,详细解析)
把上面化解一下
变为2b与a+c

  • 代码:
package pojriver;

import java.util.Arrays;
import java.util.Scanner;

public class Pojriver {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int T=sc.nextInt();  //T组数据
		for(int i=0;i<T;i++) {
			int n=sc.nextInt();
			int[] speed=new int[n];
			for(int j=0;j<n;j++) {
				speed[j]=sc.nextInt();
			}
			//排序
			Arrays.sort(speed);
			f(n,speed);  //对速度快慢进行排序
		}
	}
private static void f(int n,int[] speed) {
	int left=n;
	int ans=0;
	while(left>0) {
		if(left==1) { //只有一个人
			ans+=speed[0];
			break;
		}else if(left==2) {  //只有2人
			ans+=speed[1];
			break;
		}
		else if(left==3) { //有3个人
			ans+=speed[2]+speed[0]+speed[1];
			break;
		}
		else {
			//1,2出发,1返回,最后两名出发,2返回
			int s1=speed[1]+speed[0]+speed[left-1]+speed[1];
			//1,3出发,1返回,1,4出发,1返回,1,2过河
			int s2=speed[left-1]+speed[left-2]+2*speed[0]; //a+2b+c
			ans+=min(s1,s2);
			left-=2;  //左侧是渡河起点,left代表左侧的剩余人数
		}
	}
	System.out.println(ans);
}
private static int min(int s1, int s2) {
	return 0;
}
}

相关标签: Java 贪心