堆做法 代码
/*
* Project: 0x17_二叉堆
* File Created:Thursday, January 14th 2021, 10:33:41 am
* Author: Bug-Free
* Problem:AcWing 145. 超市
*/
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e4 + 10;
int n;
pair<int, int> a[N];
priority_queue<int> heap; //默认大根堆, 因此可以把所有的值都取负
void Supermarket() {
for (int i = 1; i <=n; i++) {
cin >> a[i].second >> a[i].first;
}
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++) {
if (a[i].first == heap.size() && -heap.top() < a[i].second) {
heap.pop();
heap.push(-a[i].second);
continue;
}
if (a[i].first > heap.size()) {
heap.push(-a[i].second);
}
}
int ans = 0;
while (heap.size()) {
ans += heap.top();
heap.pop();
}
cout << -ans << endl;
}
int main() {
while (cin >> n) {
Supermarket();
}
return 0;
}
emm贪心那块没太看懂啊,可否稍微证明一下?
比如数据:
100 10
100 10
100 10
50 3
对于t=3的情况不是把前三个卖出去吧,应该先卖出50再卖出前三个100吧?
但是按书上表述的贪心好像就是先把前三个卖出去
我觉得表述为:”按过期时间从小到大枚举商品,如果当前商品在t时刻就要过期而目前前面卖不出去;卖得出去就尽可能卖,因为后面如果有更好的会把他在后面代替。如果卖不出去,就看看能不能替代最小值卖出去,如果能就应该替代,因为这个最小值如果不卖相当于后面都不能卖,当前值现在不卖后面也不能卖,然后决策包容一下可知当前值应该卖而最小值不卖“
cout<<-ans<<endl;
- 是什么意思?
因为是大根堆,需要把所有的值都取负,因此累加后ans的值是负数,所以要把ans取反。
其实完全可以在定义的时候就写成
priority_queue[HTML_REMOVED], greater[HTML_REMOVED]> heap;