ZJ10. 编程题3
描述
产品经理(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实现的时间点。
输入描述
输入第一行三个数N、M、P，分别表示有N个PM，M个程序员，P个idea。随后有P行，每行有4个数字，分别是PM序号、提出时间、优先等级和所需时间。全部数据范围 [1, 3000]。输出描述
输出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++ 解法, 执行用时: 7ms, 内存消耗: 524KB, 提交时间: 2022-05-14
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cstdio>
using namespace std;
typedef struct Task {
int belong;
int start;
int priority;
int need_time;
int number;
int end;
}Task;
Task A[3000], *B[3000];
int n, m, p;
class cmp {
public:
bool operator()(const Task *a, const Task* b) {
return a->priority == b->priority ? (a->need_time == b->need_time? a->start > b->start : a->need_time > b->need_time) : a->priority < b->priority;
}
};
void solve() {
// m 程序员
priority_queue<int, vector<int>, greater<int>> T;
for(int i = 0; i < m; ++i) {
T.push(0);
}
// p 对idea 进行排序
sort(B, B+p, [](const Task* a, const Task* b) {
return a->start < b->start;
});
// 等待完成的idea
int cnt = 0, idx = 0;
priority_queue<Task*, vector<Task *>, cmp> ID[n+1];
for(int i = 0; i < p; ++i) {
int t = T.top();
T.pop();
//cout<< "pre : " <<cnt << endl;
while(idx < p && B[idx]->start <= t) {
ID[B[idx]->belong].push(B[idx]);
++idx;
++cnt;
}
// cout << "idea " << i << " programmer " << t << " wait " << cnt << endl;
if(cnt == 0) {
// cout << "condition 1" << endl;
Task * x = B[idx++];
ID[x->belong].push(x);
++cnt;
while(idx < p && B[idx]->start == x->start) {
ID[B[idx]->belong].push(B[idx]);
++idx;
++cnt;
}
// cout << cnt << endl;
}
// cout << "after " << cnt << endl;
// find one
int min_time = INT_MAX, iidx = -1;
// cout << " find " << endl;
for(int i = 1; i <= n; ++i) {
if(ID[i].size() > 0)
// cout << i << " " << ID[i].top()->need_time << " " << ID[i].top()->number << endl;
if(ID[i].size() > 0 && ID[i].top()->need_time < min_time) {
min_time = ID[i].top()->need_time;
iidx = i;
}
}
Task * z = ID[iidx].top();
// cout << "p: " << t << " start: " << z->start << " need_time: " << z->need_time << " number: " << z->number << endl;
t = max(t, z->start) + z->need_time;
A[z->number].end = t;
T.push(t);
ID[iidx].pop();
--cnt;
}
for(int i = 0; i < p; ++i) {
printf("%d\n", A[i].end);
}
}
int main() {
scanf("%d%d%d", &n, &m, &p);
for(int i = 0; i < p; ++i) {
scanf("%d%d%d%d",&A[i].belong, &A[i].start, &A[i].priority, &A[i].need_time);
A[i].number = i;
B[i] = &A[i];
}
solve();
}
C++14 解法, 执行用时: 7ms, 内存消耗: 588KB, 提交时间: 2020-08-26
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;
struct Task {
int id;
int pm; // pm
int apptime; // 提出时间
int prio; // 优先级
int runtime; //运行时间
Task()
:id(-1){}
};
struct PmComparator {
// b是否优先于a执行
bool operator()(const Task &a, const Task &b) {
if (a.prio != b.prio) {
return a.prio < b.prio;
} else if (a.runtime != b.runtime) {
return a.runtime > b.runtime;
} else {
return a.apptime > b.apptime;
}
}
};
class Solution {
public:
vector<int> FinshTime(int n, int m, vector<Task> tasks) {
int p = tasks.size();
auto coder_cmp = [](const Task &a, const Task &b) {
if (a.id == -1 || b.id == -1) {
return b.id == -1;
}
if (a.runtime != b.runtime) {
return a.runtime < b.runtime;
} else {
return a.pm < b.pm;
}
};
typedef priority_queue<Task, vector<Task>, PmComparator> Taskq;
vector<Taskq> pm_tasks(n);
vector<int> res(p);
auto time_cmp = [](const Task &a, const Task &b) {
return a.apptime < b.apptime;
};
sort(tasks.begin(), tasks.end(), time_cmp);
int curtime = tasks[0].apptime;
priority_queue<int, vector<int>, std::greater<int>> coders;
for (int i = 0; i < m; i++) {
coders.push(0);
}
int finish_cnt = 0;
int add_id = 0;
while (finish_cnt < p) {
if (finish_cnt == add_id) {
// there is no task in pm_tasks
curtime = tasks[add_id].apptime;
}
curtime = max(coders.top(), curtime);
while (add_id < p && tasks[add_id].apptime <= curtime) {
const Task &t = tasks[add_id++];
pm_tasks[t.pm - 1].push(t);
}
// select one task
Task selectone;
for (const Taskq &q: pm_tasks) {
if (q.empty() == false) {
selectone = coder_cmp(q.top(), selectone) ? q.top(): selectone;
}
}
pm_tasks[selectone.pm-1].pop();
coders.pop();
coders.push(curtime + selectone.runtime);
res[selectone.id] = selectone.runtime + curtime;
finish_cnt++;
}
return res;
}
};
int main()
{
/* TEST_EQ<> test_eq; */
int n, m, p;
scanf("%d%d%d", &n, &m, &p);
vector<Task> tasks(p);
for (int i = 0; i < p; i++) {
scanf("%d%d%d%d", &tasks[i].pm, &tasks[i].apptime, &tasks[i].prio,
&tasks[i].runtime);
tasks[i].id = i;
}
Solution demo;
vector<int> res = demo.FinshTime(n, m, tasks);
for (int i = 0; i < p; i++) {
printf("%d\n", res[i]);
}
return 0;
}
C++14 解法, 执行用时: 7ms, 内存消耗: 596KB, 提交时间: 2020-08-14
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;
struct Task {
int id;
int pm; // pm
int apptime; // 提出时间
int prio; // 优先级
int runtime; //运行时间
Task()
:id(-1){}
};
struct PmComparator {
// b是否优先于a执行
bool operator()(const Task &a, const Task &b) {
if (a.prio != b.prio) {
return a.prio < b.prio;
} else if (a.runtime != b.runtime) {
return a.runtime > b.runtime;
} else {
return a.apptime > b.apptime;
}
}
};
class Solution {
public:
vector<int> FinshTime(int n, int m, vector<Task> tasks) {
int p = tasks.size();
auto coder_cmp = [](const Task &a, const Task &b) {
if (a.id == -1 || b.id == -1) {
return b.id == -1;
}
if (a.runtime != b.runtime) {
return a.runtime < b.runtime;
} else {
return a.pm < b.pm;
}
};
typedef priority_queue<Task, vector<Task>, PmComparator> Taskq;
vector<Taskq> pm_tasks(n);
vector<int> res(p);
auto time_cmp = [](const Task &a, const Task &b) {
return a.apptime < b.apptime;
};
sort(tasks.begin(), tasks.end(), time_cmp);
int curtime = tasks[0].apptime;
priority_queue<int, vector<int>, std::greater<int>> coders;
for (int i = 0; i < m; i++) {
coders.push(0);
}
int finish_cnt = 0;
int add_id = 0;
while (finish_cnt < p) {
if (finish_cnt == add_id) {
// there is no task in pm_tasks
curtime = tasks[add_id].apptime;
}
curtime = max(coders.top(), curtime);
while (add_id < p && tasks[add_id].apptime <= curtime) {
const Task &t = tasks[add_id++];
pm_tasks[t.pm - 1].push(t);
}
// select one task
Task selectone;
for (const Taskq &q: pm_tasks) {
if (q.empty() == false) {
selectone = coder_cmp(q.top(), selectone) ? q.top(): selectone;
}
}
pm_tasks[selectone.pm-1].pop();
coders.pop();
coders.push(curtime + selectone.runtime);
res[selectone.id] = selectone.runtime + curtime;
finish_cnt++;
}
return res;
}
};
int main()
{
/* TEST_EQ<> test_eq; */
int n, m, p;
scanf("%d%d%d", &n, &m, &p);
vector<Task> tasks(p);
for (int i = 0; i < p; i++) {
scanf("%d%d%d%d", &tasks[i].pm, &tasks[i].apptime, &tasks[i].prio,
&tasks[i].runtime);
tasks[i].id = i;
}
Solution demo;
vector<int> res = demo.FinshTime(n, m, tasks);
for (int i = 0; i < p; i++) {
printf("%d\n", res[i]);
}
return 0;
}
C++ 解法, 执行用时: 8ms, 内存消耗: 596KB, 提交时间: 2020-12-23
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;
struct Task {
int id;
int pm; // pm
int apptime; // 提出时间
int prio; // 优先级
int runtime; //运行时间
Task()
:id(-1){}
};
struct PmComparator {
// b是否优先于a执行
bool operator()(const Task &a, const Task &b) {
if (a.prio != b.prio) {
return a.prio < b.prio;
} else if (a.runtime != b.runtime) {
return a.runtime > b.runtime;
} else {
return a.apptime > b.apptime;
}
}
};
class Solution {
public:
vector<int> FinshTime(int n, int m, vector<Task> tasks) {
int p = tasks.size();
auto coder_cmp = [](const Task &a, const Task &b) {
if (a.id == -1 || b.id == -1) {
return b.id == -1;
}
if (a.runtime != b.runtime) {
return a.runtime < b.runtime;
} else {
return a.pm < b.pm;
}
};
typedef priority_queue<Task, vector<Task>, PmComparator> Taskq;
vector<Taskq> pm_tasks(n);
vector<int> res(p);
auto time_cmp = [](const Task &a, const Task &b) {
return a.apptime < b.apptime;
};
sort(tasks.begin(), tasks.end(), time_cmp);
int curtime = tasks[0].apptime;
priority_queue<int, vector<int>, std::greater<int>> coders;
for (int i = 0; i < m; i++) {
coders.push(0);
}
int finish_cnt = 0;
int add_id = 0;
while (finish_cnt < p) {
if (finish_cnt == add_id) {
// there is no task in pm_tasks
curtime = tasks[add_id].apptime;
}
curtime = max(coders.top(), curtime);
while (add_id < p && tasks[add_id].apptime <= curtime) {
const Task &t = tasks[add_id++];
pm_tasks[t.pm - 1].push(t);
}
// select one task
Task selectone;
for (const Taskq &q: pm_tasks) {
if (q.empty() == false) {
selectone = coder_cmp(q.top(), selectone) ? q.top(): selectone;
}
}
pm_tasks[selectone.pm-1].pop();
coders.pop();
coders.push(curtime + selectone.runtime);
res[selectone.id] = selectone.runtime + curtime;
finish_cnt++;
}
return res;
}
};
int main()
{
/* TEST_EQ<> test_eq; */
int n, m, p;
scanf("%d%d%d", &n, &m, &p);
vector<Task> tasks(p);
for (int i = 0; i < p; i++) {
scanf("%d%d%d%d", &tasks[i].pm, &tasks[i].apptime, &tasks[i].prio,
&tasks[i].runtime);
tasks[i].id = i;
}
Solution demo;
vector<int> res = demo.FinshTime(n, m, tasks);
for (int i = 0; i < p; i++) {
printf("%d\n", res[i]);
}
return 0;
}
C++14 解法, 执行用时: 8ms, 内存消耗: 604KB, 提交时间: 2020-04-06
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;
struct Task {
int id;
int pm; // pm
int apptime; // 提出时间
int prio; // 优先级
int runtime; //运行时间
Task():id(-1){}
};
struct PmComparator {
// b是否优先于a执行
bool operator()(const Task &a, const Task &b) {
if (a.prio != b.prio)
return a.prio < b.prio;
else if (a.runtime != b.runtime)
return a.runtime > b.runtime;
else
return a.apptime > b.apptime;
}
};
class Solution {
public:
vector<int> FinshTime(int n, int m, vector<Task> tasks) {
int p = tasks.size();
auto coder_cmp = [](const Task &a, const Task &b)
{
if (a.id == -1 || b.id == -1)
return b.id == -1;
if (a.runtime != b.runtime)
return a.runtime < b.runtime;
else
return a.pm < b.pm;
};
typedef priority_queue<Task, vector<Task>, PmComparator> Taskq;
vector<Taskq> pm_tasks(n);
vector<int> res(p);
auto time_cmp = [](const Task &a, const Task &b) {
return a.apptime < b.apptime;
};
sort(tasks.begin(), tasks.end(), time_cmp);
int curtime = tasks[0].apptime;
priority_queue<int, vector<int>, std::greater<int>> coders;
for (int i = 0; i < m; i++)
coders.push(0);
int finish_cnt = 0;
int add_id = 0;
while (finish_cnt < p)
{
if (finish_cnt == add_id)
curtime = tasks[add_id].apptime;
curtime = max(coders.top(), curtime);
while (add_id < p && tasks[add_id].apptime <= curtime)
{
const Task &t = tasks[add_id++];
pm_tasks[t.pm - 1].push(t);
}
Task selectone;
for (const Taskq &q: pm_tasks)
if (q.empty() == false)
selectone = coder_cmp(q.top(), selectone) ? q.top(): selectone;
pm_tasks[selectone.pm-1].pop();
coders.pop();
coders.push(curtime + selectone.runtime);
res[selectone.id] = selectone.runtime + curtime;
finish_cnt++;
}
return res;
}
};
int main()
{
int n, m, p;
scanf("%d%d%d", &n, &m, &p);
vector<Task> tasks(p);
for (int i = 0; i < p; i++)
{
scanf("%d%d%d%d", &tasks[i].pm, &tasks[i].apptime, &tasks[i].prio,&tasks[i].runtime);
tasks[i].id = i;
}
Solution demo;
vector<int> res = demo.FinshTime(n, m, tasks);
for (int i = 0; i < p; i++)
printf("%d\n", res[i]);
return 0;
}