当前位置：首页 > news >正文

每日c/c++题备战蓝桥杯（洛谷P1190 [NOIP 2010 普及组] 接水问题）

news 2025/5/5 9:26:23

洛谷P1190 [NOIP 2010 普及组] 接水问题题解

题目描述

P1190 接水问题是NOIP 2010普及组的模拟题。题目大意如下：

有n个人要接水，每个水龙头同时只能供1个人使用。每个学生的接水时间已知，当某个水龙头空闲时，下一个等待的学生会立即使用该水龙头。求所有人接完水的总时间。

输入格式：

第一行两个整数n,m（1≤m≤n≤10000）
第二行n个整数，表示每个学生的接水时间

输出格式：

一个整数，表示总时间

解题思路

本题是典型的离散事件模拟问题，核心在于维护每个水龙头的可用时间，并动态分配学生到最早空闲的水龙头。

关键观察点

水龙头分配策略：当多个水龙头空闲时，应优先选择结束时间最早的水龙头（贪心策略）
时间推进方式：按最小时间单位逐步推进，每次处理所有当前时刻结束的任务

算法选择

优先队列（堆）：天然支持快速获取最小值，适合维护水龙头的可用时间
模拟法：直接按时间步进模拟每个学生的接水过程

代码解析（附用户代码讲解）

以下是用户提供的代码的逐层解析：

#include<bits/stdc++.h>
using namespace std;int n,m;
int stu[10005]={};  // 存储每个学生的接水时间
int water[105]={0};  // 记录每个水龙头当前服务的学生编号（0表示空闲）void f() {int tem=0;// 初始化前m个水龙头（当m<=n时）for(int i=1;i<=m;++i) {if(i<=n) {tem++;water[i] = i;  // 分配前m个学生到对应水龙头}}int time=0;int cet=tem+1;  // 下一个待分配的学生编号int fla=1;       // 模拟进程标志while(fla) {fla=0;// 遍历所有水龙头for(int i=1;i<=tem;++i) {if(water[i]!=0) {  // 当前水龙头正在使用中fla=1;stu[water[i]]--;  // 减少剩余时间// 接水完成if(stu[water[i]]==0) {if(cet<=n) water[i] = cet++;  // 分配下一个学生else water[i] = 0;      // 无学生可分配}}}if(!fla) break;  // 所有水龙头空闲时结束time++;          // 时间推进1单位}cout<<time;
}int main() {cin>>n>>m;for(int i=1;i<=n;++i) cin>>stu[i];f();return 0;
}

代码特点分析

直接模拟法：通过逐时间单位推进，维护每个水龙头的状态
空间复杂度：O(n+m)，适合题目给定范围
时间复杂度：O(n*m)，最坏情况下（如所有学生接水时间相同）需要遍历所有水龙头

优化方案：优先队列实现

使用优先队列可将时间复杂度优化至O(n log m)：

#include<bits/stdc++.h>
using namespace std;int main() {int n, m;cin >> n >> m;priority_queue<int, vector<int>, greater<int>> pq;  // 最小堆// 初始化m个水龙头的结束时间为0for(int i=0; i<m; ++i) pq.push(0);int res = 0;for(int i=0; i<n; ++i) {int t;cin >> t;int end_time = pq.top();pq.pop();res = max(res, end_time + t);  // 更新最大结束时间pq.push(end_time + t);}cout << res;return 0;
}