接水问题

题目描述

水房里有 $m$ 个龙头，每个龙头每秒供水 $1$ 。 $n$ 名同学按编号 $1$ 到 $n$ 的固定顺序接水， $i$ 号同学的接水量为 $w_i$ 。开始时 $1$ 到 $m$ 号同学各占一个龙头同时接水；每当某位同学接完，排队的第一位同学立刻接替他的位置（换人瞬间完成，不浪费水）。若当前接水人数不足 $m$ ，则只有这些龙头供水。问所有人接完水需要多少秒。

输入：第 1 行两个整数 $n, m$ ；第 2 行 $n$ 个整数 $w_1,\dots,w_n$ 。

输出：一行一个整数，表示接水所需的总时间（秒）。

样例 1：5 3，4 4 1 2 1 → 输出 4。样例 2：8 4，23 71 87 32 70 93 80 76 → 输出 163。

思路

由于完成即换人，龙头不空转，每个龙头的完工时刻就是分给它的 $w$ 之和，总时间等于各龙头累计接水量的最大值。新人的落点由题面唯一确定——接替刚完成的人，即累计接水量最小的龙头，故用最小堆维护各龙头的累计量：前 $\min(n,m)$ 人依次入堆，之后每人弹出堆顶 $t$ 、压回 $t+w_i$ ，最后取堆中最大值。复杂度 $O(n\log m)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 00:57
# update_at: 2026-09-30 01:04

import sys
from collections.abc import Iterable
from heapq import heapify, heapreplace


def finish_time(loads: list[int], taps: int) -> int:
    """返回所有人接完水的总秒数。

    规则等价于：新人补到"累计接水量最小"的龙头（它最先空出来，其它龙头都还在忙）。
    题面直接规定了落点，没有需要搜索的目标；龙头不空转，所以每个龙头的完工时刻就是
    分给它的 w 之和，答案取这些累计量的最大值。堆里存的就是各龙头的累计接水量。
    """
    earliest = loads[:taps]  # 前 taps 个人先各占一个龙头；n < m 时堆自然更小
    heapify(earliest)
    for load in loads[taps:]:
        heapreplace(earliest, earliest[0] + load)  # 最早空出的龙头立刻接这位同学
    return max(earliest, default=0)


def solve() -> None:
    """读入 n、m 和 n 个接水量，输出总接水时间。"""
    data: Iterable[bytes] = iter(sys.stdin.buffer.read().split())
    n, m = int(next(data)), int(next(data))
    loads = [int(next(data)) for _ in range(n)]
    print(finish_time(loads, m))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 06:12
 * update_at: 2026-10-05 06:12
 */
// main.cpp：接水问题，用最小堆维护各龙头累计接水量。
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

typedef long long ll;

// 小根堆：存放每个正在供水的龙头的累计接水量，堆顶就是最早空出来的龙头
priority_queue<ll, vector<ll>, greater<ll> > loads;

int main() {
    ll n, m;
    scanf("%lld %lld", &n, &m);
    ll ans = 0;
    for (ll i = 1; i <= n; i++) {
        ll w;
        scanf("%lld", &w);
        if (i <= m) {
            // 开始时前 m 名同学各占一个龙头（n < m 时只占 n 个龙头）
            loads.push(w);
        } else {
            // 队首同学接到"最早空出的龙头"上：换掉堆顶的累计量
            ll t = loads.top();
            loads.pop();
            loads.push(t + w);
        }
    }
    // 龙头不空转，总时间就是各龙头累计接水量的最大值
    while (!loads.empty()) {
        ans = max(ans, loads.top());
        loads.pop();
    }
    printf("%lld\n", ans);
    return 0;
}

目录

题目描述

思路

参考代码