自动搬运

查看原文

来自洛谷，原作者为

	Taduro 失落映衬黑暗，火焰燃尽光明

搬运于2025-08-24 21:43:45，当前版本为作者最后更新于2018-08-15 14:37:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题是一道带反悔的贪心，第一次遇到这种思路的题赶紧发个题解纪念一下。 首先思路就是先按时间排序（不是那个1e8啊，是截止日期），然后如果一个工作有时间去做，就先做了它（听起来有点怪），然后把它的价值压入一个小根堆。当我们找到一个没法做却价值比当前堆顶高的工作时，我们就放弃那个最小的工作，用做它的时间去做这个价值更高的工作。

另外，这题似乎不能用一般的单调队列做？（求不打脸）因为维护队列单调性的时候要删去一些元素，这样就无法支持题目所要求的修改。（或者用dp+单调队列？）

#include<queue>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
	int tim,mny;
}w[100001];
int n,i;
long long ans;
priority_queue<int,vector<int>,greater<int> > q;
bool cmp(node a,node b){
	return a.tim<b.tim;
}
int main(){
	scanf("%d",&n);
	for (i=1; i<=n; i++)
		scanf("%d%d",&w[i].tim,&w[i].mny);
	sort(w+1,w+n+1,cmp);
	for (i=1; i<=n; i++){
		if (w[i].tim<=q.size()){
			if (w[i].mny>q.top()){
				ans-=q.top();
				q.pop(); q.push(w[i].mny);
				ans+=w[i].mny;
			}
		}
		else{
			q.push(w[i].mny);
			ans+=w[i].mny;
		}
	}
	printf("%lld",ans);
	return 0;
}