贪心算法解决小船问题

 小船问题：

有一个数组arr，每个数代表每一个坐船人的体重，还有一个limit，代表小船的最大载重，每艘船限坐两人，求最少要多少船。

对问题进行分析，首先，我们对数组进行排序，先考虑两种极端情况；

如果数组最小值大于船最大载重的一半，那么说明不能进行两人合坐一艘船的情况。直接返回数组的长度；

如果数组的最大值小于等于船最大载重的一半，那么说明任何两个人都可以合坐一艘船，直接返回数组长度的一半。（因为要向上取整，可以直接  return  （arr.length + 1）/2 ;）

对于一半的情况，我们需要对数组进分组处理，将其分为大于limit / 2（记为A） 和小于等于 limit / 2（记为B），对A数组进行从小到大的遍历，对B数组进行从大到小的遍历；

将A，B两数组提取出来的结果进行取和，若和小于limit，则lessUsed++；（lessUsed表示分别在A，B两个不同的数组，但可以两人合坐一条船的数量）

若和大于limit，则将A数组左移，同时lessUnused++；（lessUnused表示在B数组，但是无法和A数组的人一起合坐，只能和B组合坐一条船的人）

最后，A组剩下的人，可以用arr.length - lessR - 1 -lessUsed表示。

在A或B任何一个数组到达尽头时，我们将可以lessUsed, (lessUnused +1)/ 2 ,和A数组剩下的数据加在一起返回即可。

 public static int minBoat(int []arr ,int limit){
        //  对arr 进行排序
        if (arr == null || arr.length == 0){
            return  0;
        }

        if (arr[arr.length -1] <= limit/2 ){  // 如果任何人的体重小于等于船的一半，说明任何人可以两两坐船。
            return (arr.length + 1)/2;
        }

        if (arr[0] > limit/2){   //如果所有人的体重大于船的一半，说明无法一起坐。
            return arr.length;
        }

        int lessR = -1;
        for (int i = arr.length -1 ;i >= 0; i--){
            if (arr[i] <= (limit /2)){
                lessR = i;
                break;
            }
        }

        int L = lessR;
        int R = lessR +1;
        int lessUnused = 0;
        while(L >= 0){
            int solved = 0;
            while(R < arr.length && arr[L] + arr[R] <= limit){
                R++;
                solved++;
            }
            if (solved == 0){
                lessUnused++;
                L--;
            }else {
                L = Math.max(-1, L-solved);
            }
        }

        int lessAll = lessR +1;
        int lessUsed = lessAll - lessUnused;
        int moreUnsolved = arr.length - lessR - 1 -lessUsed;
        return  lessUsed + ((lessUnused + 1) >> 1) + moreUnsolved;
      }