对标：CCF GESP 5级

贪心思想的原理、适用场景与经典案例

所谓贪心思想，是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法以其独特的策略和高效的执行方式而闻名，有着重要的作用。

本文将探讨C++中贪心思想的原理和适用场景，及竞赛中贪心算法的经典案例。

1. 贪心思想的原理

贪心算法是一种在求解最优化问题时采取的策略。其核心思想是：在每一步选择中，都采取当前最优的选择，通过一系列局部最优解达到全局最优解。贪心算法因时间复杂度较低，被广泛用与大规模数据处理。

2.贪心思想的适用场景

贪心算法适合以下场景：

• 排队接水问题
• 独木舟问题
• 背包问题

3.经典案例

3.1 排队接水

题目描述

有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。

输入格式

共两行，第一行为n(1≤n≤1000)；第二行分别表示第1个人到第n个人每人的接水时间T1，T2，…，Tn，每个数据之间有1个空格。

输出格式

有两行，第一行为一种排队顺序，即1到n的一种排列(如果接水时间相同，排队顺序小的在前面)；第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。

输入输出样例

输入

10
56 12 1 99 1000 234 33 55 99 812

输出

3 2 7 8 1 4 9 6 10 5
291.90

解析：

假设排队顺序为第1、第2...第n个人，他们的接水时间分别为 T₁, T₂, ..., Tₙ。

• 第1个人的等待时间就是他自己的接水时间：T₁。

• 第2个人必须等第1个人接完，所以他的等待时间是：T₁ + T₂。

• 第3个人的等待时间是：T₁ + T₂ + T₃。

• ...

• 第n个人的等待时间是：T₁ + T₂ + ... + Tₙ。

将所有人的等待时间加起来，总等待时间 = T₁ × n + T₂ × (n-1) + T₃ × (n-2) + ... + Tₙ × 1。

从公式可见，排在最前面的人（T₁）的接水时间会被后续所有的人等待，因此它对总时间的影响最大。为了让总和最小，必须让接水时间最短的任务放在最前面，以减少其被放大的效应。这就像在偿还一笔高利率的债务，越早还清，产生的总利息就越少。

示例代码：

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

struct Person {
    int id;     // 人的编号
    int time;   // 接水时间
};

// 自定义排序规则
bool cmp(const Person &a, const Person &b) {
    if (a.time == b.time) {
        return a.id < b.id; // 接水时间相同，编号小的优先
    }
    return a.time < b.time; // 否则接水时间短的优先
}

int main() {
    int n;
    cin >> n;
    vector<Person> people(n);
    
    // 输入数据，记录初始编号
    for (int i = 0; i < n; i++) {
        cin >> people[i].time;
        people[i].id = i + 1; // 编号从1开始
    }
    
    // 排序
    sort(people.begin(), people.end(), cmp);
    
    // 输出最优排队顺序
    for (int i = 0; i < n; i++) {
        cout << people[i].id << " ";
    }
    cout << endl;
    
    // 计算总等待时间
    long long totalWaitTime = 0;
    long long currentSum = 0;
    // 注意：这里i从0到n-2，因为最后一个人接水时不需要被其他人等待
    for (int i = 0; i < n - 1; i++) {
        currentSum += people[i].time; // 当前已累计的接水时间
        totalWaitTime += currentSum;  // 这个累计时间就是下一个人需要等待的时间
    }
    
    // 计算并输出平均等待时间，保留两位小数
    double averageTime = (double)totalWaitTime / n;
    cout << fixed << setprecision(2) << averageTime << endl;
    
    return 0;
}

3.2 独木舟

题目描述

旅行社计划组织一个独木舟旅行。租用的独木舟都是一样的，最多乘两人，而且载重有一个限度。现在要节约费用，所以要尽可能地租用最少的舟。本题的任务是读入独木舟的载重量，参加旅行的人数以及个人的体重，计算出所需要的独木舟数目。

输入格式

第1行是w(80 <=w <=200)，表示每条独木舟最大的载重量
第2行是正整数n(1 <=n <=30000)，表示参加旅行的人数
接下来的n行，每行是一个正整数ti(5 <=ti <=w)，每个人的重量

输出格式

输出一行一个数，表示最少的独木舟数目

输入输出样例

输入

100
9
90
20
20
30
50
60
70
80
90

输出

6

解析：

这个问题要求每条独木舟最多载两人，且总重量不超过载重上限。要让使用的船数最少，就要尽可能让更多人两两组合，避免让体重较轻的人单独占用一条船。

贪心策略如下：

1. 排序预处理：将所有人的体重按升序排序。

2. 双指针配对：使用两个指针 i和 j，分别指向当前最轻和最重的人。

   • 若 weight[i] + weight[j] <= w（即最轻和最重的人可同乘一船），则他们共用一条船。i右移，j左移，船数加1。

   • 若重量和超重，说明最重的人无法与任何人同船（否则会超重），他必须单独一船。j左移，船数加1。

3. 终止条件：当 i > j时，所有人已分配完毕。

这种策略的正确性在于：让最重的人优先配对，若最重的人能与最轻的人同船，这样能最大程度地“消耗”掉体重较大的人，避免他们占用额外的船。若最重的人无法与最轻的人同船，他只能单独乘船。

示例代码：

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

const int MAX_N = 30000; // 定义最大人数
int weights[MAX_N];      // 存储每个人的体重

int main() {
    int w, n;
    cin >> w; // 读入独木舟最大载重量
    cin >> n; // 读入人数
    for (int i = 0; i < n; i++) {
        cin >> weights[i]; // 读入每个人的体重
    }
    
    // 将体重按升序排序
    sort(weights, weights + n);
    
    int i = 0, j = n - 1; // 双指针：i指向最轻的人，j指向最重的人
    int boatCount = 0;     // 计数使用的独木舟数量
    
    // 当还有人未分配时循环
    while (i <= j) {
        if (weights[i] + weights[j] <= w) {
            // 最轻和最重的人可以同乘一条船
            i++; // 最轻的人已分配，指针右移
            j--; // 最重的人已分配，指针左移
        } else {
            // 最重的人无法与最轻的人同船，最重的人单独乘一条船
            j--; // 仅最重的人分配一条船
        }
        boatCount++; // 每次循环（无论哪种情况）都使用了一条船
    }
    
    cout << boatCount << endl;
    return 0;
}

---

温馨提示：请留下点赞！