ZJ15. 任务调度
描述
产品经理(PM)有很多好的idea，而这些idea需要程序员实现。现在有N个PM，在某个时间会想出一个 idea，每个 idea 有提出时间、所需时间和优先等级。对于一个PM来说，最想实现的idea首先考虑优先等级高的，相同的情况下优先所需时间最小的，还相同的情况下选择最早想出的，没有 PM会在同一时刻提出两个 idea。
同时有M个程序员，每个程序员空闲的时候就会查看每个PM尚未执行并且最想完成的一个idea,然后从中挑选出所需时间最小的一个idea独立实现，如果所需时间相同则选择PM序号最小的。直到完成了idea才会重复上述操作。如果有多个同时处于空闲状态的程序员，那么他们会依次进行查看idea的操作。
求每个idea实现的时间。
输入描述
输入第一行三个数N、M、P，分别表示有N个PM，M个程序员，P个idea。随后有P行，每行有4个数字，分别是PM序号、提出时间、优先等级和所需时间。输出描述
输出P行，分别表示每个idea实现的时间点。示例1
输入:
2 2 5 1 1 1 2 1 2 1 1 1 3 2 2 2 1 1 2 2 3 5 5
输出:
3 4 5 3 9
C++ 解法, 执行用时: 3ms, 内存消耗: 424KB, 提交时间: 2021-08-03
#include<bits/stdc++.h>
struct idea {
int id, pm, start, priority, time;
idea(int _id, int _pm, int _start, int _priority, int _time) {
id = _id; pm = _pm; start = _start; priority = _priority; time = _time;
}
bool operator<(const idea &i) const {
if (start == i.start) {
if (priority == i.priority) {
if (time == time) {
return pm < i.pm;
} else { return time < i.time; }
} else { return priority < i.priority; }
} else { return start < i.start; }
}
};
int f[3010];
int main() {
std::priority_queue<int, std::vector<int>, std::greater<int> > heap;
std::vector<idea> ideas;
int N, M, P, pm, start, priority, time;
scanf("%d%d%d", &N, &M, &P);
for (int i = 1; i <= P; ++i) {
scanf("%d%d%d%d", &pm, &start, &priority, &time);
ideas.push_back(idea(i, pm, start, priority, time));
}
std::sort(ideas.begin(), ideas.end());
for (int _ = 0; _ < M; ++_) { heap.push(1); }
for (auto i : ideas) {
int tt = heap.top(); heap.pop();
if (tt < i.start) { tt = i.start; }
heap.push(tt+i.time);
f[i.id] = tt+i.time;
}
for (int i = 1; i <= P; ++i) { printf("%d\n", f[i]); }
return 0;
}
C++ 解法, 执行用时: 3ms, 内存消耗: 432KB, 提交时间: 2021-09-05
#include<bits/stdc++.h>
struct idea {
int id, pm, start, priority, time;
idea(int _id, int _pm, int _start, int _priority, int _time) {
id = _id; pm = _pm; start = _start; priority = _priority; time = _time;
}
bool operator<(const idea &i) const {
if (start == i.start) {
if (priority == i.priority) {
if (time == time) {
return pm < i.pm;
} else { return time < i.time; }
} else { return priority < i.priority; }
} else { return start < i.start; }
}
};
int f[3010];
int main() {
std::priority_queue<int, std::vector<int>, std::greater<int> > heap;
std::vector<idea> ideas;
int N, M, P, pm, start, priority, time;
scanf("%d%d%d", &N, &M, &P);
for (int i = 1; i <= P; ++i) {
scanf("%d%d%d%d", &pm, &start, &priority, &time);
ideas.push_back(idea(i, pm, start, priority, time));
}
std::sort(ideas.begin(), ideas.end());
for (int _ = 0; _ < M; ++_) { heap.push(1); }
for (auto i : ideas) {
int tt = heap.top(); heap.pop();
if (tt < i.start) { tt = i.start; }
heap.push(tt+i.time);
f[i.id] = tt+i.time;
}
for (int i = 1; i <= P; ++i) { printf("%d\n", f[i]); }
return 0;
}