贪心_HDOJ4864_Task

点此打开题目页面

思路分析:

    根据对于用时为x, 级别为y的任务的酬劳为500 * x + y, 且y的最大值为100, 显然应该优先完成耗时长的任务, 考虑下面的贪心策略:

将所有任务以时间为第一关键字, 级别为第二关键字按照非递减排序得任务序列A[1...M], 依次考察A[1]...A[M], 对于每个任务, 选择可以完成该任务且级别最低的机器, 最终所有机器均被选择或A[1...M]均被考察后即得到可完成的最多任务数和可获得的最大酬劳, 通过证明每次选择后都存在一个包含当前选择的最优(完成任务数最多的同时获利最大)方案, 具体证明过程此处不再赘述, 下面给出AC代码:

//HDOJ4864_Task
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <deque>
using namespace std;
const int MAX = 1e5 + 5;
pair<int, int> task[MAX];//first:执行时间, second:级别
deque<int> ma[101];//ma[i]级别为i的所有机器
int main(){
	int N, M; 
	while(cin >> N >> M){	
		for(int i = 0; i <= 100; ++i) ma[i].clear();//一定注意要清空ma[0...100]	
		for(int i = 1, s, t; i <= N; ++i) scanf("%d %d", &s, &t), ma[t].push_back(s);
		for(int i = 0; i <= 100; ++i) 
			if(!ma[i].empty()) sort(ma[i].begin(), ma[i].end(), greater<int>());
		for(int i = 1; i <= M; ++i) scanf("%d %d", &task[i].first, &task[i].second);
		sort(task + 1, task + M + 1, greater<pair<int, int> >());
		long long ans = 0, cnt = 0;
		for(int i = 1, j; i <= M; ++i){
			for(j = task[i].second; j <= 100 && (ma[j].empty() || ma[j].front() < task[i].first); ++j);
			if(j <= 100) ans += 500 * task[i].first + 2 * task[i].second, ++cnt, ma[j].pop_front();	
		}
		cout << cnt << " " << ans << endl;
	}
	return 0;
}