从食堂打饭到银行排队：用‘接水问题’讲透贪心与优先队列（附NOIP真题C++代码）

weixin_30621959

332人浏览 · 2026-06-08 16:13:36

weixin_30621959 · 2026-06-08 16:13:36 发布

从食堂窗口到算法竞赛：用生活智慧破解"接水问题"

1. 当排队遇上算法：生活中的资源分配难题

中午12点的学校食堂总是人声鼎沸，十几个打饭窗口前蜿蜒着长长的队伍。聪明的你会怎么做？观察每个窗口的队伍长度，然后选择最短的那一列——这就是最朴素的"贪心算法"在生活中的应用。类似的场景无处不在：银行叫号系统、超市收银台、地铁安检通道...这些日常现象背后，都隐藏着一个经典的算法问题："接水问题"。

在信息学奥赛(NOIP)中，"接水问题"是考察算法思维的经典题目。题目描述很简单：有n个同学需要接水，m个水龙头，每个同学接水需要的时间不同。如何安排接水顺序，才能使所有同学接水的总时间最短？这与食堂打饭的排队策略如出一辙——总是选择当前最快能服务完上一个人的窗口(水龙头)。

为什么这个问题值得深入探讨？

它完美展现了从实际问题到算法模型的抽象过程
涉及贪心算法和优先队列两大核心算法思想
是理解时间复杂度优化的绝佳案例
在各类编程竞赛(如NOIP、CSP)中频繁出现变种题目

2. 贪心策略：像选择食堂窗口一样选择水龙头

2.1 最直观的解决方案：循环查找

想象你在食堂，会不自觉地扫视所有窗口的队伍长度，然后选择最短的那一列。对应到接水问题，我们可以用同样的策略：

初始化一个数组 time 记录每个水龙头的可用时间
对于每个同学：
- 遍历所有水龙头，找到 time 值最小的(即最早空闲的)
- 将该同学分配到这个水龙头
- 更新该水龙头的 time 值(加上该同学的接水时间)
最后，所有水龙头 time 中的最大值就是总完成时间

用C++实现这个逻辑非常简单：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m, w[10005], time[105] = {}, mx = 0;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) cin >> w[i];
    
    for(int i = 1; i <= n; ++i) {
        int mni = 1;
        for(int j = 1; j <= m; ++j) 
            if(time[j] < time[mni]) mni = j;
        time[mni] += w[i];
    }
    
    for(int i = 1; i <= m; ++i) 
        mx = max(mx, time[i]);
    cout << mx;
    return 0;
}

提示：这种方法的时间复杂度是O(nm)，当n和m较大时(比如n=10000,m=100)，循环次数将达到百万级，可能成为性能瓶颈。

2.2 贪心算法的正确性证明

为什么这种"总是选择当前最早空闲的水龙头"的策略能得到最优解？我们可以从以下几个方面理解：

无后效性 ：当前的选择不会影响后续选择的自由度
局部最优导致全局最优 ：每一步都做出最优选择，最终结果也是最优的
资源利用最大化 ：确保没有水龙头在可以工作时处于空闲状态

3. 优先队列：像智能叫号系统一样高效管理

3.1 从循环查找到堆优化

回到食堂场景，如果食堂有100个窗口，每次都要从头到尾查看一遍显然效率低下。现实中，银行叫号系统用电子显示屏实时显示各窗口状态，让我们一眼就能找到最快可用的窗口。在算法中，**优先队列(堆)**就是这样的"智能显示屏"。

优先队列可以在O(1)时间内获取最小值，插入和删除操作只需O(log m)时间，远优于循环查找的O(m)时间。对于m较大的情况，这种优化将带来显著的性能提升。

3.2 优先队列的实现方式

在C++中，我们可以使用 priority_queue 来实现：

#include <bits/stdc++.h>
using namespace std;

int main() {
    priority_queue<int, vector<int>, greater<int>> pq; // 小顶堆
    int n, m, w[10005], ans = 0;
    cin >> n >> m;
    
    for(int i = 1; i <= n; ++i) cin >> w[i];
    for(int i = 1; i <= m; ++i) pq.push(w[i]);
    
    for(int i = m+1; i <= n; ++i) {
        pq.push(pq.top() + w[i]);
        pq.pop();
    }
    
    while(!pq.empty()) {
        ans = max(ans, pq.top());
        pq.pop();
    }
    cout << ans;
    return 0;
}

两种写法的对比：

特性	循环查找法	优先队列法
时间复杂度	O(nm)	O(n log m)
代码复杂度	简单	中等
适合场景	m较小(n≤1000,m≤10)	m较大(n和m都≥1000)
空间复杂度	O(m)	O(m)

3.3 优先队列的内部工作原理

优先队列通常使用二叉堆实现，它具有以下性质：

父节点的值总是小于或等于子节点的值(最小堆)
插入操作：将新元素放到末尾，然后"上浮"到合适位置
删除操作：移除根节点，将最后一个元素移到根部，然后"下沉"

这种结构保证了我们总能高效地获取当前最小的元素。

4. 实战演练：NOIP真题解析

让我们看一道NOIP真题的具体应用：

题目描述 ：学校有n个学生要接水，有m个水龙头。第i个学生接水需要t_i秒。所有学生必须按顺序接水，不能插队。如何安排使所有学生接完水的时间最早？

输入格式 ：第一行两个整数n和m 第二行n个整数，表示每个学生的接水时间

输出格式 ：一个整数，表示最早完成时间

样例输入 ：

5 3
4 5 3 2 1

样例输出 ：

解题步骤 ：

初始化3个水龙头的时间为0
第一个学生选择任意水龙头，假设选择1号，时间变为4
第二个学生选择当前时间最小的水龙头(2号或3号)，选择2号，时间变为5
第三个学生选择3号水龙头，时间变为3
第四个学生选择当前时间最小的水龙头(3号，时间为3)，分配后时间变为3+2=5
第五个学生选择时间最小的水龙头(1号，时间为4)，分配后时间变为4+1=5
最终三个水龙头的时间分别为5,5,5，最大值为6

代码实现 （使用优先队列）：

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

int main() {
    int n, m;
    cin >> n >> m;
    priority_queue<int, vector<int>, greater<int>> pq;
    
    for(int i = 0; i < m; ++i) pq.push(0);
    
    while(n--) {
        int t; cin >> t;
        int earliest = pq.top(); pq.pop();
        pq.push(earliest + t);
    }
    
    int ans = 0;
    while(!pq.empty()) {
        ans = max(ans, pq.top());
        pq.pop();
    }
    cout << ans;
    return 0;
}