[NOIP2010-普及] 接水问题

题目描述

学校有 $m$ 个龙头， $n$ 名同学按顺序接水，第 $i$ 人需接 $w_i$ 秒。开始第 $1\sim m$ 人各占一个龙头同时接水；某人第 $x$ 秒结束后，队首下一人第 $x+1$ 秒立刻顶上。求所有人接完水需要多少秒。

输入： $n\ m$ ，然后 $n$ 个整数 $w_i$ 。
输出：一个整数，总时间。
数据范围： $1\le n\le 10000,\ 1\le m\le 100,\ 1\le w_i\le 100$ 。

思路

把每个龙头抽象为「下一次空闲时刻」，用小根堆维护这 $m$ 个时刻。依次处理每名同学：取出堆顶（最早空闲的龙头），占用 $w_i$ 秒后把新的结束时刻压回堆。答案为所有龙头结束时刻的最大值。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16import sys
import heapq

def main() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    w = [next(data) for _ in range(n)]
    # 小根堆维护 m 个龙头的“当前占用截止时刻”；初始都为 0，即 m 个龙头在第 0 秒空闲
    taps = [0] * m
    for x in w:
        # 取最早空闲的龙头，该同学从下一秒开始接 x 秒
        t = heapq.heapreplace(taps, taps[0] + x)
    # 答案 = 最后一个龙头完成时刻
    print(max(taps))

main()

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70/**
 * 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-06 14:26
 * update_at: 2026-10-06 14:26
 */
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 10005;
const int MAXM = 105;

ll w[MAXN];       // 每个同学的接水量
ll taps[MAXM];    // 每个龙头的当前占用结束时刻，下标从1开始
int n, m;

// 小根堆上浮
typedef ll heap_type;

void push_up(int idx) {
    while (idx > 1) {
        int fa = idx >> 1;
        if (taps[fa] <= taps[idx]) break;
        swap(taps[fa], taps[idx]);
        idx = fa;
    }
}

// 小根堆下沉
void push_down(int idx, int sz) {
    while ((idx << 1) <= sz) {
        int son = idx << 1;
        if (son + 1 <= sz && taps[son + 1] < taps[son]) son++;
        if (taps[idx] <= taps[son]) break;
        swap(taps[idx], taps[son]);
        idx = son;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> w[i];

    // 初始 m 个龙头都空闲，结束时刻为 0
    int sz = m;
    for (int i = 1; i <= m; i++) taps[i] = 0;
    // 建堆
    for (int i = m >> 1; i >= 1; i--) push_down(i, sz);

    // 依次处理 n 个同学，每次把最早空闲的龙头占用 w[i] 秒
    for (int i = 1; i <= n; i++) {
        ll t = taps[1];          // 堆顶：最早空闲时刻
        taps[1] = t + w[i];      // 该同学占用后新的结束时刻
        push_down(1, sz);        // 维护堆性质
    }

    // 答案为所有龙头结束时刻的最大值
    ll ans = 0;
    for (int i = 1; i <= m; i++)
        if (taps[i] > ans) ans = taps[i];
    cout << ans << '\n';
    return 0;
}

[NOIP2010-普及] 接水问题

目录

题目描述

思路

参考代码