漂流船问题

1. 如果两人的体重<=limit就右移右指针，直到people
   [L]无法再与右半部分的人配对，此时能够搞定右边rightSolved个人就表示左边也能搞定rightSolved个人，占用rightSolved条船。然后左指针向左移动rightSolved个位置。
2. 如果一个右边的人都配对不了，就增加一个左半部分搞不定的人leftNoSolved，左移左指针，直到左指针越界。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {
    public static void main(String
[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String
[] strs = br.readLine().split(" ");
        int n = strs.length;
        int
[] people = new int
[n];
        for(int i = 0; i < n; i++){
            people
[i] = Integer.parseInt(strs
[i]);
        }
        Arrays.sort(people);
        int limit = Integer.parseInt(br.readLine());
        int lessR = lowerBound(people, limit >> 1);     // 找到最后一个小于等于limit/2的位置
        int L = lessR;
        if(L == n){
            // 全是小于limit/2的体重，直接两个人一艘船
            System.out.println((n + 1) >> 1);
        }else{
            int R = L + 1;
            int leftNoSolved = 0;      // 左边没搞定的人
            int rightSolved = 0;       // 右边搞定的人
            while(L >= 0){
                while(R < n && people
[L] + people
[R] <= limit){
                    R++;
                    rightSolved++;
                }
                if(rightSolved == 0){
                    // L和右边的人配对一个都搞不定
                    leftNoSolved++;      // 添加一个没搞定的人
                    L--;                 // 左移左指针
                }else{
                    L = Math.max(-1, L - rightSolved);
                }
            }
            int leftAll = lessR + 1;
            int rightUnsolved = n - leftAll - rightSolved;
            System.out.println(rightSolved + ((leftNoSolved + 1) >> 1) + rightUnsolved);
        }
    }
    
    private static int lowerBound(int
[] nums, int target) {
        int left = 0, right = nums.length, index = right;
        while(left < right){
            int mid = left + ((right - left) >> 1);
            if(nums
[mid] > target){
                right = mid - 1;
            }else{
                index = mid;
                left = mid + 1;
            }
        }
        return index;
    }
}

import java.util.*;
public class Main{
    public static int boat(int[] weights,int max){
        Arrays.sort(weights);
        int i=0;
        int j=weights.length-1;
        int num=0;//记录所需船数
        while(i<j){
            if(weights[i]+weights[j]<=max){//配对成功
                num++;//两人给一条船
                i++;
                j--;
            }
            else{//体重超出限制，依次找较轻的
                num++;//胖的单独给一条船
                j--;
            }
        }
        if(i==j) num++;//剩下的那个人给一条船
        return num;
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String[] str=sc.nextLine().split(" ");
        int[] arr=new int[str.length];
        for(int i=0;i<str.length;i++){
            arr[i]=Integer.parseInt(str[i]);
        }
        int max=sc.nextInt();
        System.out.println(boat(arr,max));
    }
}