贪心算法解决小猫下山问题：最少缆车数量

贪心算法解决小猫下山问题：最少缆车数量

问题描述：

翰翰和达达饲养了 N 只小猫，这天，小猫们要去爬山。经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。翰翰和达达只好花钱让它们坐索道下山。

索道上的缆车最大承重量为 W，而 N 只小猫的重量分别是 C1、C2……CN。当然，每辆缆车上的小猫的重量之和不能超过 W。

每租用一辆缆车，翰翰和达达就要付 1 美元，所以他们想知道，最少需要付多少美元才能把这 N 只小猫都运送下山？

输入格式

第 1 行：包含两个用空格隔开的整数，N 和 W。

第 2..N+1 行：每行一个整数，其中第 i+1 行的整数表示第 i 只小猫的重量 Ci。

输出格式

输出一个整数，表示最少需要多少美元，也就是最少需要多少辆缆车。

思路：

贪心

首先将所有小猫按重量从大到小排序，然后从大到小依次考虑每只小猫，将其加入到已有的缆车中，如果加入后超过了承重量，则需要再租一辆缆车。由于是从大到小加入，所以每次加入的小猫都是可能需要再租一辆缆车的最轻的小猫，这样可以使租用缆车的数量最小。

时间复杂度： O(NlogN)，排序的时间复杂度为O(NlogN)，依次考虑每只小猫的时间复杂度为O(N)，因此总时间复杂度为O(NlogN)

空间复杂度： O(N)，使用了一个数组对小猫的重量进行保存

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n, w;
    cin >> n >> w;
    int c[n];
    for (int i = 0; i < n; i++) {
        cin >> c[i];
    }
    sort(c, c + n, greater<int>()); // 从大到小排序
    int count = 0; // 缆车数量
    int current_weight = 0; // 当前缆车上的重量
    for (int i = 0; i < n; i++) {
        if (current_weight + c[i] > w) { // 如果加入后超过了承重量
            count++; // 租一辆新的缆车
            current_weight = 0; // 重置当前缆车上的重量
        }
        current_weight += c[i]; // 将小猫加入到当前缆车中
    }
    if (current_weight > 0) { // 如果最后还有小猫在当前缆车上
        count++; // 需要再租一辆缆车
    }
    cout << count << endl; // 输出最少需要的缆车数量
    return 0;
}