牛牛游湖 解题报告

首先这个题的基本思路是，如果最重的人尽可能的和最轻的人在一起公用一艘船，那么显然这样就可以完美配对。如果最重的人和最轻的人都不能一起，那么最重的人只能自己一艘船。所以根据这个思路我们可以进行贪心，先将数组进行排序，然后设置两个指针，i=0, j=n-1, 那么 w[i]一定是最轻的，w[j]是最重的，如果w[i]+w[j] <= max_limit，那么i和j可以共用一艘船，即i++,j--；否则的话，只能j自己一艘船，即j--。
代码如下：

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param max_limit int整型 
     * @param w int整型vector 
     * @return int整型
     */
    int solve(int n, int max_limit, vector<int>& w) {
        // write code here
        sort(w.begin(), w.end());
        int i=0, j=n-1;
        int ans = 0;
        while(i <= j) {
            ans++;
            if(w[i]+w[j] <= max_limit) i++;
            j--;
        }
        return ans;
    }
};