题解：P1190 [NOIP2010 普及组] 接水问题

· · 题解

解题思路

记录每个水龙头放水的时间，由于接水的顺序是固定的故只能依次去接水。让第 i 个接水的人选择放水时间最小的水龙头。对于 n 个人每次从 m 个水龙头中获取放水时间最小的水龙头时可以选择用快速排序 O(m\log m)，打擂法 O(m) 或堆 O(\log m) 。选出最小时间并累加该水龙头的放水时间。由于 n,m 的数据范围比较小以上三种获取放水最小的水龙头的方法都可以通过本题，这里选用最快的堆的做法。

最后找到所有水龙头放水时间最长的即为所有人接完水时所花费的最短时间。

贪心策略证明：如果只有两个水龙头，两个人接水耗时为正数 a 和 b，如果第二个人不去选择未接水的水龙头，那么最终所有人接完水时花费的时间为 a 和 b，而贪心策略耗时为 \max(a, b)。必然存在 a+b>\max(a,b)，可以推广到 n 个水龙头和 m 个人的情况。

代码实现

#include<bits/stdc++.h>
using namespace std;
priority_queue<int, vector<int>, greater<int> > tap;//创建小根堆
int p[10005], n, m, k;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)                    //输入n个人接水的时间
        cin >> p[i];
    for (int i = 1; i <= m; i++)             //设置m个水龙头的放水时间为0
        tap.push(0);
    for (int i = 1; i <= n; i++) {                  //第i个人去找结束时间最短的水龙头接水
        int temp = tap.top();                       //取出用时最小的水龙头
        tap.pop();
        tap.push(temp + p[i]);                      //将放水后的水龙头入堆
    }
    for (int i = 1; i < m; i++)                     //弹出小根堆中元素只剩1个
        tap.pop();
    cout << tap.top();                              //最终留下的元素为打水所划分总时间
    return 0;
}