这个是真贪心了。

思想：贪心不用说 咱直接来看最核心的：怎么排序贪心？

“题目问最少的损失，那肯定是按照钱财排序啊！”

很可惜，这是一个错误的想法。 用一个很简单的例子就能否掉这个思想： 钱1时2，钱2时1，钱3时1，钱4时10

很显然，按照钱财排序，应该优先保住4；但是你会失去2+3=5！远不如“3--1--4”这样只会失去2的排列。

上述排序失败的理由是没有考虑对应的时间紧要 ，所以我们应该按照时间排列，再按照金钱排列。

思想讲完，再看看怎么实现。

1. 首先，我们应当使用一个结构体game来存储时限和金钱的信息。

2. 然后是结构体的排序，上述提到了使用时间来排序，return x.t < y.t;

3. 最后是使用一个priority_queue pq来自动排序金钱。因为在实践中会不断地加入必定不能拯救的金钱，所以要一直排序。

好，说完思想，来看代码吧：

#include <bits/stdc++.h>
using namespace std;

struct game
{
	int t;//时限
	int f;//金钱
};

game a[505];
int n,m;

bool cmp(game x,game y)
{
	return x.t < y.t;//排序的按照时间的紧要性
}

priority_queue<int,vector<int>,greater<int>> q;//优先队列记录不能拯救的金钱

int main()
{
	cin >> m >> n;
	int ans = 0,t;//ans统计失去的金钱
	for(int i = 1;i <= n;i++) cin >> a[i].t;
	for(int i = 1;i <= n;i++) cin >> a[i].f;
	sort(a + 1,a + n + 1,cmp);//这里排序
	t = a[1].t;
	for(int i = 1;i <= n;i++)
	{
		if(a[i].t > t)
		{
			while((int)q.size() > t)//这里的金钱载入必须失去的部分
			{
				ans += q.top();
				q.pop();
			}
			t = a[i].t;
		}
		q.push(a[i].f);//加入可能会失去的金钱
	}
	while((int)q.size() > t)//注意最后的金钱在循环里没有统计
	{
		ans += q.top();
		q.pop();
	}
	cout << m - ans << endl;//注意题目问的是能赚的最大
	return 0;
}

优美地结束~~

难度： 黄

算法标签： 贪心，优先队列。

按完成期限从小到大排序，然后遍历。遍历到的入队，如果队伍长度大于当前遍历到的数的时间期限，就将扣款最小的出队，并扣款。

时间复杂度 $O(nlogn)$ 。

双倍经验校外

双倍经验校内

#include<bits/stdc++.h>
using namespace std;
int n,m,s=0;
struct node{
	int t,f;
}d[555];
priority_queue<int,vector<int>,greater<int> > q;
bool cmp(node a,node b){
	return a.t<b.t;
}
int main(){
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;i++) scanf("%d",&d[i].t);
	for(int i=1;i<=n;i++) scanf("%d",&d[i].f);
	sort(d+1,d+n+1,cmp);
	for(int i=1;i<=n;i++){
		q.push(d[i].f);
		if(d[i].t<q.size()){
			m-=q.top();
			q.pop();
		}
	}
	printf("%d",m);
	return 0;
}