接水问题

GitHub跳转原题关系图返回列表

题意与原解析均从本地 OpenJudge 缓存迁移。

OJ: noi_openjudge

题目 ID: ch0109-15

难度:未知

标签:模拟贪心优先队列python

日期: 2026-07-30 23:01

目录

  1. 题意
  2. 思路
  3. 代码
  4. Python代码
  5. C++代码
    1. 复杂度
    2. 总结

题意

完整题面见同目录的 problem.md。

思路

最小堆保存各水龙头空闲时刻；每位新同学分配给最早空闲的水龙头。

代码

Python代码

python
import heapq

student_count, tap_count = map(int, input().split())
amounts = list(map(int, input().split()))
finish_times = amounts[:tap_count]
heapq.heapify(finish_times)
for amount in amounts[tap_count:]:
    heapq.heappush(finish_times, heapq.heappop(finish_times) + amount)
print(max(finish_times))

C++代码

cpp
#include <cstdio>

int n,m;
int w[10010];
int total = 0;
int st[110]; //每个水龙头要接的水量

int main(){
    scanf("%d%d",&n,&m);
    int nn = n;
    int i;
    for(i=1;i<=n;i++)
        scanf("%d",&w[i]);
    int head=1;

    //初始化
    for(head=1;head<=m && head <=n;head++){
        st[head] = w[head];
    }
    head = m;
    while(n>0){ //剩余人数不为0
        total++; //时间过1
        for(i=1;i<=m;i++){
            st[i]--;
            if( st[i] == 0) n--; //人数-1
            if( st[i] == 0 && head<nn){ //人接上来
                head++;
                st[i] = w[head];
            }
        }
    }
    printf("%d",total);

    return 0;
}

复杂度

总结