题意:有n个工作可以做,它们有截止日期和价值,每个工作需要一天完成,你从0时刻开始做,求最大收益。
我们肯定希望尽早完成某个任务,那么我们一天也不能闲,一天做一个任务。
于是我们将工作按截止日期从小到大排序,如果第i个工作的截止日期小于等于我们做的任务数(任务数就等于我们做到的天数,因为我们一天做一个),那么就拿它和我们做过的工作中最小的价值比较,如果它更大那就更换,因为这样收益更大。这相当于将我们完成前面工作的那天来做第i个工作,因为我们存的都是前面的工作,截止日期比当前这个小,那么能做之前的也能做这个。
对于截止日期大于我们完成的任务数的,直接加进来就行。
可以用优先队列维护。
点击查看代码
void solve() {
int n;
std::cin >> n;
using PII = std::pair<int, int>;
std::vector<PII> a(n);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i].first >> a[i].second;
}
std::sort(a.begin(), a.end());
std::priority_queue<int, std::vector<int>, std::greater<int> > heap;
i64 ans = 0;
for (int i = 0; i < n; ++ i) {
if (a[i].first <= heap.size()) {
if (heap.top() < a[i].second) {
ans = ans - heap.top() + a[i].second;
heap.pop();
heap.push(a[i].second);
}
} else {
heap.push(a[i].second);
ans += a[i].second;
}
}
std::cout << ans << "\n";
}