暑假打工 题解

1.题目

点击查看

注：一般认为一项任务当天就能完成，但只有在M天内领到报酬才算真正“做”了这项任务。所以在以下分析及代码中，一项任务在接受后第二天就能安排其他任务（即任务绝对意义上完成了），但做不做还要考虑能不能领到报酬。

2.开始做题

本人初始代码为价值9分的骗分，就不发了吧……

正解

其实是道简单的贪心，每天选择能完成的价值最大的任务，并将其完成就可以了。 具体的，需要将每项能完成的任务（即能领到报酬的）的工钱从大到小排序（这时候，要反向从最后一天枚举，逐步筛选能接受的任务），以待选择，每天选择一项任务，将所得报酬累加，就是答案。因为每天都会产生能完成的工作，如果每天都对任务的性价比排序，那时间直接爆炸，可以用优先队列，动态更新，时间复杂度会小很多。另外，如果你用结构体的形式存储每项任务的信息，想让它们排序的时候联动，需要重定义<符号，确保优先队列依据报酬进行排序。

话不多说上代码：

#include <bits/stdc++.h>
using namespace std;
const int TOP=1e5+5;
struct work
{
	int a,b;
};
int n,m;
work t[TOP];
priority_queue<work> p;
int ans;
bool operator < (work one,work tow)
{
	return one.b<tow.b;
}
bool cmp(work one,work tow)
{
	return one.a<tow.a;
}
int main()
{
	int f,k;
	cin>>n>>m;
	for(f=1;f<=n;f++)
		cin>>t[f].a>>t[f].b;
	sort(t+1,t+1+n,cmp);
	k=1;
	for(f=1;f<=m;f++)
	{
		while(k<=n&&t[k].a<=f)
		{
			p.push(t[k]);
			k++;
		}
		if(!p.empty())
		{
			ans+=p.top().b;
			p.pop();
		}
	}
	cout<<ans;
	return 0;
}

诚信做人，请勿抄袭