本文共 755 字，大约阅读时间需要 2 分钟。

第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。

每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。

返回载到每一个人所需的最小船数。(保证每个人都能被船载)。

示例 1：

输入：people = [3,2,2,1], limit = 3输出：3解释：3 艘船分别载 (1, 2), (2) 和 (3)

解题思路：先按照人的体重进行排序，再利用二分法，分别取首尾两个体重，求和与liimit比较，并计算小船数。 

                 贪婪策略：选择重量和最接近limit的两个人

public int numRescueBoats(int[] people, int limit)	{		int weightSum = 0; // 体重之和		int numOfShip = 0; // 轮船数				// 按照人的体重排序		Arrays.sort(people);				int i = 0, j = people.length-1;				// 该成员体重达到limit		while (j >= 0 && people[j] == limit)		{			j--;			numOfShip++;		}				if (j < 0)		{			return numOfShip;		}				// 二分法变形		while (i <= j)		{			if (people[i] + people[j] <= limit)			{				numOfShip++;				i++;				j--;			}			else // 说明people[j]只能独坐一艘船			{				numOfShip++;				j--;			}		}				return numOfShip;	}

转载地址：http://ocpoi.baihongyu.com/