寄居の友人c

快速過河問題：

題目大意：有n個(gè)人要過一條河，每個(gè)人過河都需要一個(gè)時(shí)間ai，有一艘船，每次過河只能最多裝兩個(gè)人。兩個(gè)人劃船過河所需的時(shí)間都取決于過河時(shí)間長的那個(gè)人。比如，A，B兩人過河所需時(shí)間分別為a，b，那么，他們成一條船過河所需的時(shí)間為：max{a，b}。現(xiàn)在讓你安排一個(gè)過河方案，讓所有人用最短的時(shí)間全部過河。此題在POJ1700上，另外洛谷P1809題類似。

既然搜了這個(gè)問題，必然懂了題意

有兩種解適用不同的情況。人數(shù)為1、2、3時(shí)不做描述，很容易得出最優(yōu)解。當(dāng)人數(shù)為4的時(shí)候：

方案一：每次都是最快的回來帶人。

方案二：最快的兩個(gè)人先去，回來其中一個(gè)人（誰都行），然后最慢的兩個(gè)人去（這樣算最慢的時(shí)間，次慢的不算），再回來另一個(gè)人（兩個(gè)最快的人還沒去），最后兩個(gè)最快的去。

當(dāng)人數(shù)大于4的時(shí)候，我想了根據(jù)想不通，怎么送？
我漏了一個(gè)很重要的方面導(dǎo)致我想不通，兩種最優(yōu)解，并不是用同一個(gè)方法求出最優(yōu)解！是根據(jù)最優(yōu)的方法，逐步求出。將求運(yùn)送四個(gè)人的方法簡單變通一下，每次只兩種方法運(yùn)送最慢的兩個(gè)人，求這個(gè)最優(yōu)解：

方案一：總是用最快的帶人，帶“次快的-次次快……次次慢-次慢-最慢”，等于“最慢-次慢-……-次次快-次快”。（每次都回來最快，所以先帶誰都一樣），就讓最快先送最慢的兩個(gè)人，時(shí)間就是：最慢和最快去，最快回，次慢最快去，最快回（最快要回來，因?yàn)檫€有人沒過去啊，最快回來兩次）= 最快*2+最慢+次慢

方案二：根據(jù)上面方案二的描述，計(jì)算的時(shí)間是：最慢+最快+次快*2（次快和最快去的，算次快的，次快還要回來，一共兩次）

根據(jù)兩種方案送最慢的兩個(gè)人。找出用時(shí)最短的。然后求剩下沒過河的人，因?yàn)樗瓦^去兩個(gè)人嘛，沒過河的就減去2，這就會(huì)產(chǎn)生兩種結(jié)果：剩下2個(gè)人和剩下3個(gè)人。正好剩下兩個(gè)人，時(shí)間就是最慢的那個(gè)人的時(shí)間；正好三個(gè)人，最快的辦法就是用方案一，最快的帶那兩個(gè)人，即：三個(gè)人的時(shí)間相加。

理解這個(gè)題，參考的文章：

https://blog.csdn.net/qq_36306833/article/details/68941731

很多人用動(dòng)規(guī)，實(shí)現(xiàn)的證明，嗯，我不會(huì)，只是通俗易懂的明白了這個(gè)貪心的奇妙之處。這個(gè)動(dòng)規(guī)的證明，去洛谷看題解吧
代碼：

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

public class 過河 {

//	有n個(gè)人，第i個(gè)人重量為wi。每艘船的最大載重量均為C，且最多只能乘兩個(gè)人。用最少的船裝載所有人。
//
//	 貪心策略：考慮最輕的人i，如果每個(gè)人都無法和他一起坐船（重量和超過C），則唯一的方案是每個(gè)人坐一艘
//	 否則，他應(yīng)該選擇能和他一起坐船的人中最重的一個(gè)j
	public static void main(String[] args) {
		int[] nums = {1,2,2,2,10};
//		Scanner sc = new Scanner(System.in);
//		int n = sc.nextInt();
//		int[] nums = new int[n];
//		for (int i = 0; i < nums.length; i++) {
//			nums[i] = sc.nextInt();
//		}

		Arrays.sort(nums);
		System.out.println(t1(nums));

	}

	static int t1(int[] nums) {
		int s = 0;
		int len = nums.length;

		while (true) {
			if (len == 1)
				return nums[0];
			if (len == 2)
				return s + Math.max(nums[0], nums[1]);
			if (len == 3) {
				return s + nums[0] + nums[1] + nums[2];
			}
			int s1 = nums[0] + nums[0] + nums[len - 1] + nums[len - 2]; // 求方案一的時(shí)間
			int s2 = nums[0] + nums[1] + nums[1] + nums[len - 1]; // 第二種
//			System.out.println(s1+"  "+s2);
			len -= 2;
			s += Math.min(s1, s2);
		}

	}
}