8.8 乘船问题 以及 贪心策略思路总结

乘船问题：

即，对每个人的重量进行从小到大排序，（从两端分别进行组合，左端指针s，右端指针e）

每次选择重量最大和最轻的两个人一起乘船s++ e-- 船数+1，还需过河的人数-2

   如果超重，则重量最大的人单独一艘船 e--，船数+1，还需过河的人数-1

代码：

import java.util.Arrays;
import java.util.Scanner;public class Main {/* */public static void main(String[] args) {//（1）输入相关数据Scanner sc = new Scanner(System.in);int n = sc.nextInt();//人数int c = sc.nextInt();//每艘船载的总重量不超过cint[] w = new int[n];//每个人的重量for(int i=0;i<n;i++) {w[i]=sc.nextInt();}//(2)排序Arrays.sort(w);//(3)寻找所需的船数int p1=0;int p2=n-1;int res=0;//需要的船数while(n>0) {//未过河的人数大于0if(n==1) {//只剩下一人res++;break;}if((w[p1]+w[p2])<=c) {//两人一起坐船p1++;p2--;res++;n-=2;}else {//重量最大超过C，单独坐船p2--;res++;n--;}}System.out.println(res);}
}

贪心策略思路总结：