【题意】给定n项工作的截止时间和价值,每项工作需要1单位时间完成,求最大价值。n<=10^5。
【算法】贪心+堆
【题解】
如果是访问到x时将d[x]前的点从价值最大的能加就加是错误的贪心,因为后面的点会占用到前面的,不能保证已选的就是最优的。
正确的贪心:按顺序选择前面所有点,并把价值取负后加入堆表示“反悔值”,然后遇到超限就弹出反悔值最小的(价值也就最小)。
还有一种思路是反过来做:从后往前算“开始时间”,每秒选择一个算入答案。
”反悔“是贪心思想的重要用法之一!
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=;
struct cyc{
int d,p;
}a[maxn];
priority_queue<int>q;
bool cmp(cyc a,cyc b){return a.d<b.d;}
int n;
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d%d",&a[i].d,&a[i].p);
sort(a+,a+n+,cmp);
long long ans=,now=;
for(int i=;i<=n;i++){
ans+=a[i].p;now++;q.push(-a[i].p);
if(now>a[i].d){now--;ans+=q.top();q.pop();}
}
printf("%lld",ans);
return ;
}