【Leetcode】881. Boats to Save People（配数学证明）

题目地址：

https://leetcode.com/problems/boats-to-save-people/description/

给定一个长$n$数组$A$，代表每个人的重量，给定一个船的载重$t$，该船最多载两个人。每一轮该船需要运人去对岸，问至少要多少趟。题目保证最重的那个人不会超过船载重。

思路是贪心。考虑最重的那个人，那个人如果加上最轻的人就超重了，则让最重的那个人自己上船，这样问题规模减少了$1$，问题解决。如果这个最重的人$x_1$可以和最轻的人$y_1$一起上，那么这两个人一起上也可以得到最优解，原因是，如果最优解里$x_1$和$y_2$一起上的，如果$y_1$单独坐，那么可以强行让$y_1,y_2$对换，这样船数不变，也可以；如果$y_1$和$x_2$一起上船的，那么由于$x_1\ge x_2,y_1\le y_2,x_1+y_2\le t\Rightarrow x_1+y_1\le t,x_2+y_2\le t$，从而也可以强行让$y_1,y_2$对换。这样可以一步步将最优解调整为贪心解。代码如下：

class Solution {
 public:
  int numRescueBoats(vector<int>& p, int t) {
    int res = 0;
    sort(p.begin(), p.end());
    for (int l = 0, r = p.size() - 1; l <= r; r--) {
      if (l < r && p[l] + p[r] <= t) l++;
      res++;
    }

    return res;
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度$O(n\log n)$，空间$O(1)$。