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

思路：

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

CPP

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

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

否则，把所有接水量用小根堆中的

push

存进堆中，再一一将最小接水量

pop

出堆。这样也就可以了。

code：

CPP

#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;
}

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

文章操作

思路：

code：

相关推荐

评论

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