信息学奥赛一本通 1233：接水问题 | 1950：【10NOIP普及组】接水问题 | OpenJudg

【题目链接】

ybt 1233：接水问题

ybt 1950：【10NOIP普及组】接水问题

OpenJudge NOI 1.9 15:接水问题

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

【题目考点】

1. 模拟

【解题思路】

接水顺序确定，接水规则确定，整个接水流程就已经确定了，不需要通过算法决定任何事情，这是一个考察模拟的题。

设数组time，time[i]表示第i个水龙头可以使用的时刻。

time数组中最小值的下标为mni，那么当前情况下一定是第mni号水龙头先给上一个人接完水后空了出来，下一个人就该在第mni号水龙头接水。

假设第i人要接水，取time数组中最小值的下标为mni，那么第x人就该在第mni个水龙头接水，第mni号水龙头的可以使用时刻增加wiw_iwi​，即time[mni] += w[i];

遍历每个人，确定每个人接水的水龙头位置，而后遍历time数组，取其中的最大值，即为所有同学都接完水的时刻。

至于求最小值的过程，有两种方法：

解法1：使用循环求最小值

整体复杂度为O(nm)O(nm)O(nm)

解法2：借助优先队列（堆）求最小值

整体复杂度为O(nlogm)O(nlogm)O(nlogm)。

【题解代码】

解法1：循环求最小值

#include <bits/stdc++.h>using namespace std;int main(){int n, m, w[10005], time[105] = {}, mx = 0;//time[i]:在第i个水龙头接水结束的时间 cin >> n >> m;for(int i = 1; i <= n; ++i)cin >> w[i];for(int i = 1; i <= n; ++i){int mni = 1;//time中最小值的下标 for(int j = 1; j <= m; ++j)if(time[j] < time[mni])mni = j;time[mni] += w[i];//第mni水龙头接水结束时间增加w[i] }for(int i = 1; i <= n; ++i)mx = max(mx, time[i]);cout << mx;return 0;}

解法2：使用优先队列求最小值

#include <bits/stdc++.h>using namespace std;struct Pair{int n, t;//n:水龙头编号 t:结束时间Pair(){}Pair(int a, int b):n(a),t(b){}bool operator < (const Pair &b) const{return b.t < t;//结束时间早更优先 } };int main(){priority_queue<Pair> pq;int n, m, w[10005], mni, mx = 0;cin >> n >> m;for(int i = 1; i <= n; ++i)cin >> w[i];for(int i = 1; i <= m; ++i)pq.push(Pair(i, w[i]));for(int i = m+1; i <= n; ++i)//已知m<=n {int mni = pq.top().n, t = pq.top().t;pq.pop();pq.push(Pair(mni, t + w[i]));//第mni水龙头接水结束时间增加w[i]}while(pq.empty() == false){mx = max(mx, pq.top().t);pq.pop();}cout << mx;return 0;}

信息学奥赛一本通 1233：接水问题 | 1950：【10NOIP普及组】接水问题 | OpenJudge NOI 1.9 15 | 洛谷 P1190 [NOIP 普及组] 接水问题