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

GSQ0829 · 2025-01-07 13:03:17 · 题解

思路：

这题，我采用了小根堆的方式来做。

priority_queue<int, vector<int>, greater<int> >p;

那么，如果接水人数不大于龙头个数，那最大接水量就是答案。

否则，把所有接水量用小根堆中的 push 存进堆中，再一一将最小接水量 pop 出堆。这样也就可以了。

code：

#include <bits/stdc++.h>
using namespace std;

int n, m, t, minn = 0, maxn = 0;
priority_queue<int, vector<int>, greater<int> >p;

int main() {
    cin >> n >> m;
    if (n <= m) {
        for (int i = 1; i <= n; i++) {
            cin >> t;
            maxn = max(t, maxn);
        }
    } else {
        for (int i = 1; i <= m; i++) {
            cin >> t;
            p.push(t);
        }
        for (int i = m + 1; i <= n; i++) {
            cin >> t;
            minn = p.top();
            p.pop();
            p.push(t + minn);
        }
        for (int i = 1; i <= m; i++) {
            maxn = p.top();
            p.pop();
        }
    }
    cout << maxn << endl;
    return 0;
}