[37]安排机器-腾讯2018秋
2018-10-28 本文已影响73人
jdzhangxin
1.题目描述
小Q的公司最近接到m个任务, 第i个任务需要xi的时间去完成, 难度等级为yi。小Q拥有n台机器, 每台机器最长工作时间zi, 机器等级wi。
对于一个任务,它只能交由一台机器来完成, 如果安排给它的机器的最长工作时间小于任务需要的时间,则不能完成,如果完成这个任务将获得 200 * xi + 3 * yi 收益。
对于一台机器,它一天只能完成一个任务, 如果它的机器等级小于安排给它的任务难度等级, 则不能完成。
小Q想在今天尽可能的去完成任务, 即完成的任务数量最大。如果有多种安排方案,小Q还想找到收益最大的那个方案。小Q需要你来帮助他计算一下。
- 输入描述：
输入包括N + M + 1行,
输入的第一行为两个正整数n和m(1 <= n,m <= 100000), 表示机器的数量和任务的数量。
接下来n行,每行两个整数zi和wi(0 < zi < 1000,0 <= wi <= 100), 表示每台机器的最大工作时间和机器等级。
接下来的m行,每行两个整数xi和yi(0 < xi < 1000,0 <= yi<= 100), 表示每个任务需要的完成时间和任务的难度等级。 - 输出描述：
输出两个整数, 分别表示最大能完成的任务数量和获取的收益。 - 输入示例：
1 2 100 3 100 2 100 1 - 输出示例：
1 20006
2.题目解析
贪心法(每个任务在满足级别和时长的同时，要选择级别最低用时最少的机器)
具体步骤：
- 先把机器和任务按照时长和等级降序排序，时长优先。
- 遍历任务，记录时长大于当前任务的所有机器的级别。(因为任务已经按时长降序排列，所以，这些机器也大于后面的任务的时长，即可以被后面的任务使用)
- 从任务等级开始遍历，从记录中选出等级最低的机器完成任务。（在记录中的机器，时长都满足后面任务需要，具体时长的长短已经不重要，机器级别变成一个影响后面任务需要的重要因素，所以选择最小适合的等级。）
能完成长时长高难度的机器，也可以完成短时长低难度的任务。
3.参考答案
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int max_grade = 100; // 最高级别
struct Node {
int duration, grade;// 时长和等级
};
int cmp(Node a, Node b) {
if (a.duration == b.duration)
return a.grade > b.grade;
return a.duration > b.duration;
}
int main() {
int n = 0; // 机器数量
int m = 0; // 任务数量
scanf("%d%d", &n, &m);
// 每台机器的最大工作时间和机器等级
Node machines[n];
for (int i = 0; i < n; i++)
scanf("%d%d", &machines[i].duration, &machines[i].grade);
// 每个任务需要的完成时间和任务的难度等级
Node tasks[m];
for (int i = 0; i < m; i++)
scanf("%d%d", &tasks[i].duration, &tasks[i].grade);
// 机器排序(时长优先排序)
sort(machines, machines + n, cmp);
// 任务排序(时长优先排序)
sort(tasks,tasks + m, cmp);
int count = 0; // 最大能完成的任务数量
LL res = 0; // 获取的收益
int cnt[max_grade+1];// 记录级别机器数量，下标为机器等级，值为机器数目
memset(cnt, 0, sizeof(cnt));
for (int i = 0, j = 0; i < m; i++) { // 遍历任务
// 找到所有满足时长的机器，并记录级别
for(;j < n && machines[j].duration >= tasks[i].duration;j++) {
cnt[machines[j].duration]++;// 记录满足时长的机器等级
}
for (int k = tasks[i].grade; k <= max_grade; k++) {// 找到可用级别最小的机器
if (0 != cnt[k]) { // 如果分配到机器
count++;// 统计完成任务数
cnt[k]--;
res += 200 * tasks[i].duration + 3 * tasks[i].grade; // 计算总收益
break;
}
}
}
printf("%d %lld\n", count, res);
return 0;
}
