「一本通 1.1 练习 4」家庭作业（带反悔的贪心）

发表于 更新于 分类于

题目来源：《信息学奥赛一本通·提高篇》

提供题目的OJ：LOJ

题目链接：「一本通 1.1 练习 4」家庭作业

本题目的基本算法——贪心，具体说是带反悔的贪心。

题目大意：你有n个项目，每个项目有一定的期限和价值，规定只有在期限内完成这个项目才能获得相应的价值，完成一个项目需要花一个时间单位，求能获得的最大价值。

基本思路：带反悔的贪心，先按照期限升序排序，用一个变量记录时间，然后枚举每一个项目，如果时间在期限以内，将价值存入一个小根堆中，如果超出期限，与小根堆的top()进行比较，如果大于top()，则将top()扔掉，加入当前的价值。

因为时间原因，代码不写注释了，感觉思路已经很明确了。。。

附件：代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
struct HM {
	int tim,dis;
	bool operator < (const HM &x) const {
		return tim<x.tim;
	}
}a[1000010];
int n,ans,Time=1;
bool pd[1000010];
priority_queue <int, vector <int>, greater <int> > q;
namespace DY {
	void main() {
		scanf("%d",&n);
		for(int i=1; i<=n; i++) {
			scanf("%d%d",&a[i].tim,&a[i].dis);
		}
		sort(a+1,a+1+n);
		for(int i=1; i<=n; i++) {
			if(Time<= a[i].tim)
				Time++,q.push(a[i].dis);
			else if(a[i].dis>q.top())
				q.pop(),q.push(a[i].dis);
		}
		while(!q.empty()) {
			int x=q.top(); q.pop();
			ans+=x;
		}
		printf("%d",ans);
	}
};
int main() {
	DY::main();
	return 0;
}