产品经理(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实现的时间点。
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
没什么难度，主要就是理解。
本套试题AC 代码在 https://github.com/ReyzalX/nowcoder 查看。
#include <bits/stdc++.h>
using namespace std;
struct Task
{
int id;
int pm;
int time;
int pri;
int dur;
};
vector<vector<Task>> pmtasks;
map<int, int> result;
int proid = 1;
struct Programer
{
Programer()
{
t = 0;
this->id = proid++;
}
int t;//当前的时间
int id;
int doTask()
{
vector<Task>::iterator findT;
int index = -1;
for (size_t i = 0; i < pmtasks.size(); i++)
{
auto& tasks = pmtasks.at(i);
if (tasks.size() == 0) continue;
auto it = tasks.begin();
while (it!= tasks.end() && it->time > t)
it++;
if (it == tasks.end()) continue;
if (index == -1)
{
findT = it;
index = i;
}
else
{
if (it->dur < findT->dur)
{
findT = it;
index = i;
}
}
}
if (index != -1)
{
t += findT->dur;
result[findT->id] = t;
pmtasks.at(index).erase(findT);
return 1;
}
else
t++;
return 0;
}
};
int main()
{
int n, m, p;
cin >> n >> m >> p;
pmtasks.resize(n);
for (size_t i = 0; i < p; i++)
{
Task task;
cin >> task.pm >> task.time >> task.pri >> task.dur;
task.id = i;
pmtasks.at(task.pm - 1).push_back(task);
}
for (size_t i = 0; i < pmtasks.size(); i++)
{
auto& tasks = pmtasks.at(i);
if (tasks.size() == 0) continue;
sort(tasks.begin(), tasks.end(), [](Task & t1, Task & t2)
{
if (t1.pri == t2.pri)
{
if (t1.dur == t2.dur)
{
return t1.time < t2.time;
}
else return t1.dur < t2.dur;
}
else return t1.pri > t2.pri;
});
}
vector<Programer> pros(m);
while (p > 0)
{
sort(pros.begin(), pros.end(), [&](Programer & t1, Programer & t2)
{
return t1.t < t2.t;
});
p -= pros.begin()->doTask();
}
for (auto &it : result)
cout << it.second << endl;
return 0;
}
题意：多个PM生成多个任务，多个coder处理任务，任务有开始时间、优先级、 运行时常、PM编号等信息。题意关键是如何保证，多个空闲coder同时 处理多个任务，可以设置一个数组，表示每个coder的当前的空闲时刻。 循环实现只要还存在未处理的任务，选出最早空闲的coder处理该任务。当然 需要找出该coder空闲时刻之前所有未处理的任务，按照规则选出一个任务进行处理。 注意存在一种情况就是有的任务的提出时间非常晚，多个coder 空闲的时候没有任务可做，需要等待最早出现的任务出现。import java.util.*;
import java.io.*;
class Node{
int noPM;
int begin;
int priority;
int time;
boolean flag;
public Node(int noPM, int begin, int priority, int time) {
super();
this.noPM = noPM;
this.begin = begin;
this.priority = priority;
this.time = time;
}
}
public class Main {
static long res=0;
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
int numPM=s.nextInt();
int coder=s.nextInt();
int n=s.nextInt();
int i,j;
Node ideas[]=new Node[n];
int minBegin=Integer.MAX_VALUE;
for(i=0;i<n;i++){
ideas[i]=new Node(s.nextInt(),s.nextInt(),s.nextInt(),s.nextInt());
minBegin=Math.min(minBegin, ideas[i].begin);
}
//逻辑不清晰,主要体现在“如何体现同时工作”
//每一个woker都有自己的空闲时间，每次取出一个最早空闲的woker处理任务，可以实现同时工作
int t=1;
TreeMap<Integer,ArrayList<Integer>>map=new TreeMap<Integer,ArrayList<Integer>>();//用于存储每个PM的idea集合
int worker[]=new int[coder];//每一个worker空闲时的时间
for(i=0;i<worker.length;i++)
worker[i]=minBegin;
int count=n;
TreeMap<Integer,Integer>res=new TreeMap<Integer,Integer>();
while(count>0){//只要存在还未完成的idea
//将worker按照当前空闲时间进行排序，数值较小的表示较早空闲，
Arrays.sort(worker);
int curtime=worker[0];
boolean b=false;
int curminBegin=3001;
for(i=0;i<ideas.length;i++){//依次查看任务
if(ideas[i].flag==true)
continue;
if(ideas[i].begin>curtime)//如果任务还没有产生
{
curminBegin=Math.min(curminBegin, ideas[i].begin);
continue;
}
int no=ideas[i].noPM;
if(map.get(no)==null){
b=true;
ArrayList<Integer>list=new ArrayList<Integer>();
list.add(i);
map.put(no, list);
}else{
map.get(no).add(i);
}
}//将所有当前空闲时间之前产生的任务收集起来
if(!b){
//空闲的时候没有任务
for(i=0;i<worker.length;i++)
if(worker[i]<curminBegin)
worker[i]=curminBegin;
continue;
}
ArrayList<Integer>bestPM=new ArrayList<Integer>();
for(int key:map.keySet()){ //对每个pm的任务取出最优任务
ArrayList<Integer>pmNo=map.get(key);
int bestindex=pmNo.get(0);
for(i=1;i<pmNo.size();i++){
int index=pmNo.get(i);
if(ideas[index].priority>ideas[bestindex].priority)
bestindex=index;
else if(ideas[index].priority==ideas[bestindex].priority){
if(ideas[index].time<ideas[bestindex].time)
bestindex=index;
else if(ideas[index].time==ideas[bestindex].time){
if(ideas[index].begin<ideas[bestindex].begin)
bestindex=index;
}
}
}
bestPM.add(bestindex);
}
//从所有最优idea中选出最终目标
int bestindex=bestPM.get(0);
for(i=1;i<bestPM.size();i++){
int index=bestPM.get(i);
if(ideas[index].time<ideas[bestindex].time)
bestindex=index;
else if(ideas[index].time==ideas[bestindex].time){
if(ideas[index].noPM<ideas[bestindex].noPM)
bestindex=index;
}
}
ideas[bestindex].flag=true;
worker[0]+=ideas[bestindex].time;
res.put(bestindex, worker[0]);
count--;
map.clear();
}
for(int key:res.keySet()){
System.out.println(res.get(key));
}
}
}
# N个PM，M个程序员，P个idea
N, M, P=(int(x) for x in input().split())
# 输入：PM序号、提出时间、优先等级和所需时间
# 优先级：优先等级>所需时间>PM序号，当前时间要大于等于提出时间
tasks=[[int(x) for x in input().split()] + [i] for i in range(P)]
# 按提出时间排序
tasks.sort(key=lambda x: x[1])
# 工人工作时长
now_M=[0]*M
now_time=1
now_tasks={}
output=[]
while len(output)<P:
# 找最近空闲程序员
min_M_index = now_M.index(min(now_M))
# 跳过忙碌时间
if now_time<now_M[min_M_index]:
now_time=now_M[min_M_index]
# 找当前时间可用任务
while len(tasks)>0:
task = tasks[0]
if task[1]<=now_time:
if task[0] in now_tasks:
now_tasks[task[0]].append(task)
else:
now_tasks[task[0]]=[task]
tasks.remove(task)
else:
break
# 找每个PM优先级最高的任务
last_tasks=[]
for task_key in now_tasks.keys():
if len(now_tasks[task_key])>0:
now_tasks[task_key].sort(key=lambda x: (-x[2], x[3], x[1]))
last_tasks.append(now_tasks[task_key][0])
if len(last_tasks)==0:
now_time+=1
continue
last_tasks.sort(key=lambda x: (x[3], x[0]))
task=last_tasks[0]
now_tasks[task[0]].remove(task)
now_M[min_M_index]=now_time+task[3]
output.append([task[4],now_M[min_M_index]])
output.sort(key=lambda x: x[0])
for i in output:
print(i[1]) 
#python3完美AC，思路参见https://github.com/JosFang/exercise/blob/master/%E5%AD%97%E8%8A%82%E8%B7%B3%E5%8A%A82018%E6%A0%A1%E6%8B%9B%E7%AE%97%E6%B3%95%E7%AC%94%E8%AF%95%EF%BC%88%E7%AC%AC%E4%B8%80%E6%89%B9%EF%BC%89/T3.py
def find_finsh_time(time_ideas, n_chengxuyuan, n_idea):
time = 0
zhixining_ideas = []
finsh_ideas = []
pm_ideas_dic = {}
n_xinyou_ideas = 0
while True:
time += 1
if zhixining_ideas != []:
deleted_ideas = []
for i in zhixining_ideas:
i[3] -= 1
if i[3] == 0:
deleted_ideas.append(i)
for i in deleted_ideas:
zhixining_ideas.remove(i)
n_chengxuyuan += 1
i.append(time) # 5:执行完成时间
finsh_ideas.append(i)
if zhixining_ideas == [] and n_idea == 0:
break
for t in time_ideas:
if t == time:
for i in time_ideas[t]:
if i[0] not in pm_ideas_dic:
pm_ideas_dic[i[0]] = []
pm_ideas_dic[i[0]].append(i)
n_xinyou_ideas += 1
break
while n_chengxuyuan > 0 and n_xinyou_ideas > 0:
pm_want_idea = []
for i in pm_ideas_dic:
if pm_ideas_dic[i] != []:
pm_want_idea.append(min(pm_ideas_dic[i], key=lambda s: (-s[2], s[3], s[1])))
if pm_want_idea != []:
want_idea = min(pm_want_idea, key=lambda s: (s[3], s[0]))
zhixining_ideas.append(want_idea)
pm_ideas_dic[want_idea[0]].remove(want_idea)
n_idea -= 1
n_xinyou_ideas -= 1
n_chengxuyuan -= 1
finsh_ideas = sorted(finsh_ideas, key=lambda s: s[4])
for i in finsh_ideas:
print(i[5])
[n_pm, n_chengxuyuan, n_idea] = [int(i) for i in input().strip().split()]
time_ideas = {}
for i in range(n_idea):
# 0:pm序号，1：提出时间，2：优先等级，3：所需时间,4：任务序号
idea = [int(i) for i in input().strip().split()]
idea.append(i)
if idea[1] not in time_ideas:
time_ideas[idea[1]] = []
time_ideas[idea[1]].append(idea)
find_finsh_time(time_ideas, n_chengxuyuan, n_idea)
#include <bits/stdc++.h>
using namespace std;
typedef struct Idea {
int id,raise,pri,cost;
}Idea;
int n,m,num;
vector<vector<Idea>> pmIdea;
map<int, int> finish;
typedef struct Programmer {
int time;
Programmer() {
time=0;
}
int done() {
int index=-1;
vector<Idea>::iterator idea_search;
for (int i=0; i<pmIdea.size(); ++i) {
auto& ideas = pmIdea.at(i);
if (ideas.size()==0) continue;
auto it =ideas.begin();
for (; it!=ideas.end(); ++it) {
if (it->raise<=time) break;
}
if (it==ideas.end()) continue;
if (index==-1 || it->cost<idea_search->cost) {
idea_search = it;
index = i;
}
}
if (index!=-1) {
time += idea_search->cost;
finish[idea_search->id] = time;
pmIdea.at(index).erase(idea_search);
return 1;
}
else time++;
return 0;
}
}Programmer;
bool cmp1(Idea a, Idea b) {
if (a.pri!=b.pri) {
return a.pri>b.pri;
}
else if (a.pri==b.pri && a.cost!=b.cost) {
return a.cost<b.cost;
}
else {
return a.raise<b.raise;
}
}
bool cmp2(Programmer a, Programmer b) {
return a.time<b.time;
}
int main() {
scanf("%d%d%d", &n,&m,&num);
pmIdea.resize(n);
int a,b,c,d;
for (int i=0; i<num; ++i) {
scanf("%d%d%d%d", &a,&b,&c,&d);
pmIdea.at(a-1).push_back({i,b,c,d});
}
for (int i=0; i<n; ++i) {
auto& ideas = pmIdea.at(i);
if (ideas.size()==0) continue;
sort(ideas.begin(), ideas.end(), cmp1);
}
vector<Programmer> pro(m);
while (num>0) {
sort(pro.begin(), pro.end(), cmp2);
num -= pro.begin()->done();
}
for (auto it=finish.begin(); it!=finish.end(); ++it) {
printf("%d\n", it->second);
}
return 0;
}
理清楚逻辑就好了
#include<bits/stdc++.h>
using namespace std;
struct idea{
// idea的标号, 想出idea的pm, 想出idea的时间, idea的优先级, idea所需时间
int id, pm, time, priority, cost;
idea(int id_, int pm_, int time_, int priority_, int cost_):
id(id_),pm(pm_),time(time_),priority(priority_),cost(cost_){
}
};
// pm对idea的优先级比较
struct cmp_by_pm{
bool operator()(const idea& a, const idea& b) {
if (a.priority != b.priority) {
return a.priority < b.priority;
}
if (a.cost != b.cost) {
return a.cost > b.cost;
}
if (a.time != b.time) {
return a.time > b.time;
}
return a.pm < b.pm;
}
};
// 想出idea的时间比较
bool cmp_time(const idea& a, const idea& b){
return a.time < b.time;
}
// 程序员对idea的优先级比较
struct cmp_by_worker{
bool operator()(const idea& a, const idea& b) {
if (a.cost != b.cost) {
return a.cost > b.cost;
}
return a.pm > b.pm;
}
};
int main(){
int i;
int N, M, P;
cin >> N >> M >> P;
vector<idea> ideas; // 记录ideas
int pm, time, priority, cost;
for (int i = 0; i < P; i++) {
cin >> pm >> time >> priority >> cost;
ideas.emplace_back(idea(i, pm - 1, time, priority, cost));
}
vector<int> workers(M, 0); // 程序员剩余的工作时间
vector<int> finished(P); // 记录ideas的完成时间
// 优先队列, 分别记录每个PM当前尚未执行的idea, 可获得其最想执行的idea
priority_queue<idea, vector<idea>, cmp_by_pm> cur_ideas[N];
// 对ideas排序, 按时间逐个加入每个PM的优先队列中
sort(ideas.begin(), ideas.end(), cmp_time);
int count = 0, p = 0;
time = 1;
while (count < P) {
while (p < P && ideas[p].time <= time) {
int pm_ = ideas[p].pm;
cur_ideas[pm_].push(ideas[p]);
p++;
}
// 优先队列, 记录每个PM最想执行的idea, 可获得程序员将要做的idea
priority_queue<idea, vector<idea>, cmp_by_worker> q;
for (i = 0; i < N; i++) {
if (!cur_ideas[i].empty()) {
q.push(cur_ideas[i].top());
}
}
// 更新程序员的剩余工作时间, 为空闲程序员分配工作
for (i = 0; i < M; i++) {
if (workers[i] > 0) {
workers[i]--;
}
if (workers[i] == 0 && !q.empty()) {
idea t = q.top();
q.pop();
cur_ideas[t.pm].pop();
// 一个PM的idea被执行后, 他的次优先idea需要加入队列中
if (!cur_ideas[t.pm].empty()) {
q.push(cur_ideas[t.pm].top());
}
// 分配工作后更新剩余工作时间, 同时可确定完成时间
workers[i] = t.cost;
finished[t.id] = time + t.cost;
count++;
}
}
time++;
}
for (i = 0; i < P; i++) {
cout << finished[i] << endl;
}
}
时间点模拟即可import java.util.*; class Idea implements Comparable<Idea> { int pmid; int startTime; int proority; int speed_time; // idea的次序 int id; int chosed_time; // 被开始执行时间 int achive_time; public Idea(int pmid, int startTime, int proority, int speed_time, int id) { this.pmid = pmid; this.startTime = startTime; this.proority = proority; this.speed_time = speed_time; this.id = id; } public void setAchive_time(int achive_time) { this.achive_time = achive_time; } public void setChosed_time(int chosed_time) { this.chosed_time = chosed_time; } @Override public int compareTo(Idea o) { if (this.proority != o.proority) return -(this.proority - o.proority); else { if (this.speed_time != o.speed_time) return (this.speed_time - o.speed_time); else { if (this.startTime != o.startTime) return (this.startTime - o.startTime); } } return 0; } } // java自带的二分查找如果查不到返回的是-插入的位置，但是插入的这个位置索引是从1开始的 public class Main { /** * 每到达一个时间，需要把这个时间所提出的idea按PM号放入pm队列中，不能刚开始时全放入 * @param args */ public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); // pm数量 int m = in.nextInt(); // 程序员数量 int p = in.nextInt(); // idea数量 ArrayList<PriorityQueue<Idea>> pm = new ArrayList<>(); HashMap<Integer, ArrayList<Idea>> start_idea = new HashMap<>(); // 记录某开始时间的对应idea for (int i = 0; i < n; i++) { pm.add(new PriorityQueue<Idea>()); } ArrayList<Idea> res = new ArrayList<>(); // 0代表空闲，1代表忙 boolean[] cxy = new boolean[m]; // 对应程序员正在执行的idea Idea[] working = new Idea[m]; int pmid, start_time, proority, speed_time; for (int i = 0; i < p; i++) { pmid = in.nextInt(); start_time = in.nextInt(); proority = in.nextInt(); speed_time = in.nextInt(); if (!start_idea.containsKey(start_time)) { start_idea.put(start_time, new ArrayList<Idea>()); start_idea.get(start_time).add(new Idea(pmid, start_time, proority, speed_time, i)); } else { start_idea.get(start_time).add(new Idea(pmid, start_time, proority, speed_time, i)); } } //时间从1开始，我们使用时间点模拟来解决这个问题 int time = 1; while (res.size() < p) { /** * 0. 将新时间提出来的idea放入队列中 * 1. 先检查哪些idea已***完，如若干完则释放程序员，将干完的idea放入结果中 * 2. 遍历每个程序员，如果是空闲就派一个活 * 3. 时间+1 */ // 0. 将新时间提出来的idea放入队列中 if (start_idea.containsKey(time)) { for (Idea tp : start_idea.get(time)) { // tp.setChosed_time(time); pm.get(tp.pmid - 1).add(tp); } } //1. 先检查哪些idea已***完，如若干完则释放程序员，将干完的idea放入结果中 for (int i = 0; i < m; i++) { Idea tp = working[i]; if (cxy[i]) { if (time - tp.chosed_time == tp.speed_time) { tp.setAchive_time(time); res.add(tp); working[i] = null; cxy[i] = false; } } } // 2. 遍历每个程序员，如果是空闲就派一个活 for (int i = 0; i < m; i++) { if (cxy[i] == false) { int min_time = Integer.MAX_VALUE; PriorityQueue<Idea> chosed_pm = null; for (PriorityQueue<Idea> tp : pm) { if (tp.size() > 0 && tp.peek().speed_time < min_time) { min_time = tp.peek().speed_time; chosed_pm = tp; } } // 将idea放出pm，放入工作队列 if (chosed_pm != null) { working[i] = chosed_pm.poll(); working[i].setChosed_time(time); cxy[i] = true; } } } time++; } res.sort((a, b)->a.id - b.id); for (Idea tp : res) { System.out.println(tp.achive_time); } } }
实例能跑通，但是提交就不对了，没看出来那里错误 #定义更新程序员状态的函数 def reM_state(state): for i in range(M): if state[i]>0: state[i]=state[i]-1 else: pass return state #数据输入 #N个PM，M个程序员，P个idea。 N,M,P=map(int,input().split()) idea=[] ideafind=[] for i in range(P): idea.append(list(map(int,input().split()))) idea[i].append(i) for i in idea: ideafind.append(i) #PM序号、提出时间、优先等级和所需时间、索引 #感觉需要用到栈 以时间为循环 #程序员的状态 M_state=[0 for i in range(M)] #定义起始时间 T=0 #初始化等待安排的idea的序号 idea_index=[] #初始化答案 ans=[] #剩余的idea while len(idea)!=0: #更新时间 T=T+1 #更新程序员状态 M_state=reM_state(M_state) #更新idea的状态 #临时index indeX=[] for idea_i in idea: if idea_i[1]==T: indeX.append(idea_i) indeX.sort(key=lambda x:(x[2],x[3],x[1])) for idea_i in indeX: idea_index.append(idea_i[4]) #print(idea_index) #为程序员安排任务 for i in range(M): # print(i) if M_state[i]==0 and len(idea_index)!=0: #为程序员安排任务 M_state[i]= ideafind[idea_index[0]][3] #ans.append([idea_index[0],M_state[i]+ideafind[idea_index[0]][1]]) ans.append([idea_index[0], M_state[i] + T]) #更新idea # idea.index(ideafind[idea_index[0]]) idea.pop(idea.index(ideafind[idea_index[0]])) #更新idea_index idea_index.pop(0) ans.sort(key= lambda x:x[0]) for i in ans: print(i[1],end="\n")
N,M,P=map(int,input().split())
tasks={} #将每个任务以pm编号为键储存到字典里，仅保留未完成的任务
def findWork(clock):
#在时间是clock时给空闲的程序员寻找可做任务
doTime=3001 #记录可做任务的用时
doPm=3001 #记录可做任务属于哪一个pm
doId=3001 #记录可做任务的编号
for everyPm in tasks.keys():
#寻找每一个pm当前最想完成的任务
status=0 #记录该任务的优先等级
time=3002 #记录该任务的用时
thisRaise=3002 #记录该任务什么时候被提出
taskId=3002 #记录该任务的编号
for everyTask in tasks[everyPm].keys():
if tasks[everyPm][everyTask]['raise']<=clock:
#如果这个任务提出时间不晚于当前时间才能进行比较
if tasks[everyPm][everyTask]['status']>status:
#如果新任务优先级更高，那么选择新的任务
status = tasks[everyPm][everyTask]['status']
time = tasks[everyPm][everyTask]['time']
thisRaise = tasks[everyPm][everyTask]['raise']
taskId=everyTask
elif tasks[everyPm][everyTask]['status']==status:
if tasks[everyPm][everyTask]['time']<time:
#如果新任务用时更少，选择新任务
status = tasks[everyPm][everyTask]['status']
time = tasks[everyPm][everyTask]['time']
thisRaise = tasks[everyPm][everyTask]['raise']
taskId=everyTask
elif tasks[everyPm][everyTask]['time']==time:
if tasks[everyPm][everyTask]['raise']<thisRaise:
#如果新任务提出时间更早，选择新任务
status = tasks[everyPm][everyTask]['status']
time = tasks[everyPm][everyTask]['time']
thisRaise = tasks[everyPm][everyTask]['raise']
taskId=everyTask
#获得了当前pm最想完成的任务，与选择的任务做比较
if time<doTime:
#如果当前任务用时更少，选择新任务
doTime = time
doPm=everyPm
doId=taskId
elif time==doTime:
if everyPm<doPm:
#如果当前任务的pm编号更小，选择新任务
doTime = time
doPm=everyPm
doId=taskId
if doPm<3001:
#如果存在可做的任务，从tasks中删除这个任务
del tasks[doPm][doId]
return doTime,doId #返回可做任务的用时和编号
for i in range(P):
#task[0]是pm序号，task[1]是提出时间，task[2]是优先等级，task[3]是所需时间
task = list(map(int,input().split()))
if task[0] not in tasks:
tasks[task[0]]={} #tasks[pm编号]是一个字典，以任务编号为键储存每个任务的具体信息
tasks[task[0]][i]={'status':task[2],'raise':task[1],'time':task[3]}
finishTime=[-1 for i in range(P)] #记录每个任务的完成时间
worker=[-1 for i in range(M)] #记录每个程序员最新任务的完成时间
clock=1 #记录当前时刻
finishNum=0 #记录已完成任务的数量
while finishNum<P:
for i in range(M):
if worker[i]<=clock:
#如果第i个worker当前任务已经完成，为他寻找新的可做任务
time,taskId = findWork(clock)
if time<3001:
#如果任务存在
worker[i]=clock+time #记录程序员完成这个任务的时刻
finishTime[taskId]=clock+time #记录这个任务的完成时刻
finishNum+=1 #已完成任务+1
else:
#如果任务不存在，说明当前时刻没有可做的任务了，对之后的空闲程序员也不用寻找任务
break
clock+=1
for i in range(P):
print(finishTime[i]) import heapq line = input().split() N,M,P = int(line[0]), int(line[1]), int(line[2]) ideas = [] time_ideas = dict() ans = [0 for _ in range(P)] for i in range(P): line = list(map(int, input().split())) line[2] = -line[2] ''' pmid, proposetime, priority(inversed), timeneeded ''' line.append(i) proposetime = line[1] if proposetime in time_ideas: time_ideas[proposetime].append((line[2], line[3], line[1], line[0], line[4])) else: time_ideas[proposetime] = [(line[2], line[3], line[1], line[0], line[4])] ''' priority(inversed), timeneeded, proposetime, pmid, id ''' time = 0 nfinished = 0 tasks = [[] for _ in range(N)] idles = M endtime = [] while nfinished < P: time += 1 if time in time_ideas: for idea in time_ideas[time]: heapq.heappush(tasks[idea[3]-1], idea) while endtime and endtime[0] <= time: heapq.heappop(endtime) idles += 1 #print(time, idles, endtime) to_finish = [] for j in range(N): if tasks[j]: idea = tasks[j][0] heapq.heappush(to_finish, (idea[1], idea[3], idea[0], idea[2], idea[4])) ''' timeneeded, pmid, priority(inversed), proposetime, id ''' while idles>0 and to_finish: nextjob = heapq.heappop(to_finish) jobfinish = time + nextjob[0] heapq.heappush(endtime, jobfinish) idles -= 1 ans[nextjob[4]] = jobfinish heapq.heappop(tasks[nextjob[1]-1]) nfinished += 1 if tasks[nextjob[1]-1]: idea = tasks[nextjob[1]-1][0] heapq.heappush(to_finish, (idea[1], idea[3], idea[0], idea[2], idea[4])) for i in range(P): print(ans[i])
import java.io.BufferedInputStream; import java.util.Arrays; import java.util.Scanner; /** * @Author zhenwang.wzw * @Date 2020/7/27 下午11:15 * @Description: TODO **/ public class SelectIdea { // 产品经理(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实现的时间点。 // 2 2 5 // 1 1 1 2 // 1 2 1 1 // 1 3 2 2 // 2 1 1 2 // 2 3 5 5 public static void main(String[] args) { Scanner sc = new Scanner(new BufferedInputStream(System.in)); int n = sc.nextInt(); int m = sc.nextInt(); int p = sc.nextInt(); Idea[] orgIdeas = new Idea[p]; Idea[][] ideas = new Idea[n][3000]; Pm[] pms = new Pm[n]; Engineer[] engineers = new Engineer[m]; for(int i=0;i<n; i++) { Pm pm = new Pm(); pm.id = i; pm.ideaNum = 0; pm.canSelectEndIndex = 0; pm.leftStartIndex = 0; pms[i] = pm; } for(int i=0;i<m; i++) { Engineer engineer = new Engineer(); engineer.id = i; engineer.nextTime = 1; engineers[i] = engineer; } for(int i=0;i<p;i++) { Integer pmId = sc.nextInt() - 1; Integer createTime = sc.nextInt(); Integer priority = sc.nextInt(); Integer needTime = sc.nextInt(); Idea idea = new Idea(); idea.id = i; idea.pmId = pmId; idea.createTime = createTime; idea.priority = priority; idea.cost = needTime; orgIdeas[i] = idea; ideas[pmId][pms[pmId].ideaNum++] = idea; } /** * 1、idea按creatTime升序排序,curTime=1 * 2、engineers按nextTime，建立小跟堆 * 3、t=engineer小跟堆根节点time,curTime>=engineer.root.time,curTime不变，否则curTime=engineer.root.time,选择小跟堆根节点程序员作为执行者 * 4、curTime有变更，从leftIdeaStartIndex开始，选取time>=idea.time节点，加入可选择idea区，按有优先级重建小跟堆，(priority,cost,createTime) * 5、从各PM idea堆根节点中（canSelectIdeaEnd>0），选择needTime最小的执行（也可建立堆？） * 6、可执行idea存在，engineer.nextTime = curTime+idea.needTime,重建engineer堆，从步骤3迭代执行 * 7、可执行idea不存在，根据leftIdeaStartIndex,遍历各PM最早可执行idea，选择time最小的,设置为curTime，执行步骤3 */ for (int i=0; i< n; i++ ) { Arrays.sort(ideas[i], 0, pms[i].ideaNum, (o1, o2) -> { return o1.createTime.compareTo(o2.createTime); }); } Integer curTime = 0; boolean curTimeChange = false; Integer executeIdeaNum = 0; while (executeIdeaNum<p) { int nextTime = engineers[0].nextTime; if(curTime<nextTime) { curTime = nextTime; curTimeChange = true; } if(curTimeChange) { for(int i=0; i<n; i++) { for(int j=pms[i].leftStartIndex; j<pms[i].ideaNum; j++) { if(ideas[i][j].createTime <= curTime) { addItemToHeap(ideas[i], pms[i].canSelectEndIndex, ideas[i][j]); pms[i].canSelectEndIndex ++; pms[i].leftStartIndex = j+1; } else { break; } } } curTimeChange = false; } Integer selectPmId = null; Integer minNeedTime = Integer.MAX_VALUE; for(int i=0; i<n; i++) { if(pms[i].canSelectEndIndex>0) { Idea tmp = ideas[i][0]; if(tmp.cost <minNeedTime) { minNeedTime = tmp.cost; selectPmId = i; } } } if(selectPmId!=null) { Idea executeIdea = ideas[selectPmId][0]; executeIdea.completeTime = curTime + executeIdea.cost; executeIdeaNum++; /** * 重建pm的idea堆 */ pms[selectPmId].canSelectEndIndex --; if(pms[selectPmId].canSelectEndIndex>0) { ideas[selectPmId][0] = ideas[selectPmId][pms[selectPmId].canSelectEndIndex]; adjustHeap(ideas[selectPmId], 0, pms[selectPmId].canSelectEndIndex); } /** * 重建engineer堆 */ engineers[0].nextTime = executeIdea.completeTime; adjustHeap(engineers, 0, m); } else { Integer minCreateTime = Integer.MAX_VALUE; for(int i=0; i<n; i++) { if(pms[i].leftStartIndex<pms[i].ideaNum && ideas[i][pms[i].leftStartIndex].createTime<minCreateTime) { minCreateTime = ideas[i][pms[i].leftStartIndex].createTime; } } curTime = minCreateTime; curTimeChange = true; } } for(int i=0; i<p; i++) { System.out.println(orgIdeas[i].completeTime); } } /** * 堆中增加item，并调整堆 * @param array * @param length * @param item */ public static void addItemToHeap(Comparable[] array, int length, Comparable item) { array[length] = item; for(int i=length; i>0; i=(i-1)/2) { int r = (i -1)/2; if(array[r].compareTo(array[i]) > 0) { swap(array, r, i); } else { break; } } } /** * 根节点发生变更，自顶向下调整堆 * @param array * @param i * @param length */ public static void adjustHeap(Comparable[] array, int i, int length) { for(int k=2*i+1; k<length; k=2*i+1) { if(k+1<length && array[k+1].compareTo(array[k]) < 0) { k++; } if(array[i].compareTo(array[k]) > 0) { swap(array, i, k); i = k; } else { break; } } } private static void swap(Comparable[] array, int i, int j) { Comparable tmp = array[i]; array[i] = array[j]; array[j] = tmp; } private static class Idea implements Comparable<Idea>{ private Integer id; private Integer pmId; private Integer createTime; private Integer priority; private Integer cost; private Integer completeTime; @Override public int compareTo(Idea o) { if(this.priority.compareTo(o.priority)==0) { if(this.cost.compareTo(o.cost)==0) { return this.createTime.compareTo(o.createTime); } else { return this.cost.compareTo(o.cost); } } else { return o.priority.compareTo(this.priority); } } } private static class Engineer implements Comparable<Engineer>{ private Integer id; /** * 下次空闲时间 */ private Integer nextTime; @Override public int compareTo(Engineer o) { return this.nextTime.compareTo(o.nextTime); } } private static class Pm { int id; int ideaNum; int canSelectEndIndex; int leftStartIndex; } }
#include<bits/stdc++.h>
using namespace std;
struct Idea{
int pm;
int propose;
int prio;
int spend;
int pos;
};
bool cmp_idea(Idea &i1, Idea &i2){
if(i1.prio!=i2.prio) return i1.prio>i2.prio;
if(i1.spend!=i2.spend) return i1.spend<i2.spend;
if(i1.propose!=i2.propose) return i1.propose<i2.propose;
return i1.pm<i2.pm;
}
struct cmp_per_pm{
bool operator() (Idea &a, Idea &b){
if(a.prio!=b.prio) return a.prio<b.prio;
if(a.spend!=b.spend) return a.spend>b.spend;
return a.propose>b.propose;
}
};
struct cmp_pms{
bool operator() (Idea &a, Idea &b){
if(a.spend!=b.spend) return a.spend>b.spend;
return a.pm>b.pm;
}
};
bool sort_by_time(Idea &a, Idea &b){
return a.propose<b.propose;
}
int main(){
int n_pm, n_person, n_idea;
cin>>n_pm>>n_person>>n_idea;
vector<Idea> ideas(n_idea);
for(int i=0;i<n_idea;i++){
Idea idea;
scanf("%d%d%d%d", &idea.pm, &idea.propose,&idea.prio,&idea.spend);
idea.pos = i;
ideas[i] = idea;
}
sort(ideas.begin(), ideas.end(), sort_by_time);
vector<int> persons(n_person,0); // 记录每人的剩余工作时间
vector<int> ftime(n_idea,0); // 记录ideas的完成时间
int n_finish = 0;
int ptr=0;
priority_queue<Idea, vector<Idea>, cmp_per_pm> pm_idea[n_pm]; //为每个PM维持一个堆。堆顶是优先级最高、时间最少的idea。
for(int cur_time=1;n_finish<n_idea;){
//将时间范围内的任务，增加入对应的PM堆中。
while(ptr<n_idea && ideas[ptr].propose<=cur_time){
Idea idea = ideas[ptr++];
pm_idea[idea.pm-1].push(idea); //注意 pm_idea[idea.pm-1] 而非pm_idea[idea.pm]
}
//选择候选任务。 将每个pm的堆顶任务做堆，保持堆顶元素为时间最小pm最小的任务。
priority_queue<Idea, vector<Idea>, cmp_pms> ctask;
for(int i=0;i<n_pm;i++){
if(!pm_idea[i].empty()) {
ctask.push(pm_idea[i].top());
}
}
//找到空闲人员, 分配任务。 没有合适的任务就继续空闲。
int minff = INT_MAX;
for(int i=0;i<n_person;i++){
if(persons[i] == 0 && !ctask.empty()){
Idea idea = ctask.top();
persons[i] = idea.spend;
ftime[idea.pos] = cur_time + idea.spend;
n_finish++;
ctask.pop();
pm_idea[idea.pm-1].pop();
if(!pm_idea[idea.pm-1].empty()) ctask.push(pm_idea[idea.pm-1].top());
}
minff = min(minff, persons[i]);
}
if(minff == 0) minff = 1;
for(int i=0;i<n_person;i++){
if(persons[i]!=0) persons[i] = persons[i]-minff;
}
cur_time += minff;
}
for(int i=0;i<n_idea;i++){
cout<<ftime[i]<<endl;
}
return 0;
}
N, M, P = [int(x) for x in input().split()] nums = [] for i in range(P): nums.append([int(x) for x in input().split()]+ [i]) # Priority nums.sort(key=lambda x: x[0]) nums.sort(key=lambda x: x[3]) nums.sort(key=lambda x: x[1]) CXY_flag = [[True, 0] for _ in range(M)] zuidatichushijian = nums[-1][1] xitongshijian = 1 ideanum = 0 now_nums = [] ans = [0]*P while True: # input now idea while ideanum < P and nums[ideanum][1] == xitongshijian: now_nums.append(nums[ideanum]) ideanum += 1 # updata CXY_flag for i in range(M): if not CXY_flag[i][0]: CXY_flag[i][1] -= 1 if CXY_flag[i][1] == 0: CXY_flag[i][0] = True # Assignment of tasks for i in range(M): if CXY_flag[i][0] and now_nums: CXY_flag[i][0] = False CXY_flag[i][1] = now_nums[0][3] ans[now_nums[0][4]] = now_nums[0][3] + xitongshijian del now_nums[0] # end condition if not now_nums and xitongshijian > zuidatichushijian: break # updata xitongshijian xitongshijian += 1 # input ans for i in ans: print(i)python3，只能通过30%，有没有大佬能看看错哪了，万分感谢~~
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
