[BZOJ 1029] [JSOI2007] 建筑抢修【贪心】

浏览数：16 / 时间：2015年06月09日

题目链接：BZOJ - 1029

题目分析

使用一种贪心策略。

现将任务按照deadline从小到大排序。

然后枚举每一个任务，如果当前消耗的时间加上完成这个任务的时间不会超过这个任务的deadline，那么就完成这个任务。

否则，如果完成这个任务的时间比之前选择完成的任务中完成时间最长的一个要短，那么就弹出之前完成的那个任务，换上当前的这个任务。

这样当前的答案没有变，当前消耗的时间却减少了。

用堆来实现取最大值的操作。

代码

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>

using namespace std;

const int MaxN = 150000 + 5;

int n, Ans, Time;

struct ES
{
	int Ct, DL;
} E[MaxN];

bool Cmp(ES e1, ES e2) 
{
	return e1.DL < e2.DL;
}

priority_queue<int> Q;

int main() 
{
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d%d", &E[i].Ct, &E[i].DL);
	sort(E + 1, E + n + 1, Cmp);
	Time = 0; Ans = 0;
	while (!Q.empty()) Q.pop();
	for (int i = 1; i <= n; ++i)
	{
		if (Time + E[i].Ct <= E[i].DL) 
		{
			Time += E[i].Ct;
			Q.push(E[i].Ct);
			++Ans;
		}
		else 
		{
			if (Q.empty()) continue;
			if (E[i].Ct < Q.top()) 
			{
				Time -= Q.top();
				Q.pop();
				Time += E[i].Ct;
				Q.push(E[i].Ct);
			}
		}
	}
	printf("%d\n", Ans);
	return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

[BZOJ 1029] [JSOI2007] 建筑抢修【贪心】