Description
给定长度为\(n\)的数组\(a[]\)，每个元素\(a_i\)为\(\{p_i, d_i\}\)，其中\(p_i\)表示贡献值，\(d_i\)表示期限，每个元素的贡献需要花费\(1\)时间单位，超过期限则无法贡献。求期限内最大的总贡献值
Constraints
\(n\)不超过\(10^4\)
Solution
这道题适合作为反悔贪心的第一题
从直觉来看，按照期限\(d_i\)进行排序。维护一个小根堆，堆上按照贡献\(p_i\)作为关键字，并且假设当前时间为\(x\)，则堆大小也为\(x\)
维护反悔的过程：如果在\(d = 1\)选好了\(a_i\)，但是到了\(d = 2\)时存在2个或以上的\(a_j\)在贡献\(p_j\)上超过\(p_i\)，则执行反悔操作
Code
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct P {
int p;
int d;
bool operator < (const P& a) const {
if(d != a.d) return d < a.d;
return p > a.p;
}
};
int main() {
for(int n; cin >> n;) {
vector<P> vec(n);
for(size_t i = 0 ; i < n; ++i) {
P &v = vec[i];
cin >> v.p >> v.d;
}
sort(vec.begin(), vec.end());
int idx = 0;
int maxd = vec.back().d;
int ans = 0;
priority_queue<int, vector<int>, greater<int> > que;
for(int d = 1; d <= maxd; ++d) {
while(idx < n && vec[idx].d < d) idx++;
while(idx < n && vec[idx].d == d) {
if(que.size() < d) {
que.push(vec[idx].p);
} else if(que.size() == d) {
int smallp = que.top();
int curp = vec[idx].p;
if(smallp < curp) {
que.pop();
que.push(curp);
}
}
idx++;
}
}
while(!que.empty()) {
ans += que.top();
que.pop();
}
cout << ans << endl;
}
return 0;
}