产品经理(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
时间点模拟即可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); } } }
请问这代码哪里有错？为什么只通过了30%
import java.util.Scanner;
import java.util.List;
import java.util.PriorityQueue;
import java.util.ArrayList;
import java.util.Comparator;
public class Main {
public static void main(String []args){
int N,M,P;
Scanner in=new Scanner(System.in);
N=in.nextInt();
M=in.nextInt();
P=in.nextInt();
int [][]ideas=new int[P][];
for (int i=0;i<P;i++){
ideas[i]=new int[]{in.nextInt(),in.nextInt(),
in.nextInt(),in.nextInt(),0};
}
List ideaList=new ArrayList(P);
for (int i=0;i<P;i++){
ideaList.add(ideas[i]);
}
int timeSpot=0; //表示当前时间
int []status=new int[M]; //0表示当前程序员是空闲状态，
PriorityQueue priorityQueue=new PriorityQueue(new Comparator() {
@Override
public int compare(int[] o1, int[] o2) {
if (o1[2]!=o2[2]){
return o1[2]-o2[2];
}
else if (o1[3]!=o2[3]){
return o1[3]-o2[3];
}
else if(o1[1]!=o2[1]){
return o1[1]-o2[1];
}
return 0;
}
});
while (!ideaList.isEmpty()){
for (int i=0;i<M;i++){ //查看M个程序员的状态
if (status[i]==0){
for (int j=0;j<ideaList.size();j++){
if (ideaList.get(j)[1]<=timeSpot){
priorityQueue.add(ideaList.get(j));
}
}
if (priorityQueue.isEmpty()) break;
//为第i个程序 寻找一个idea
int []idea=priorityQueue.poll();
status[i]=idea[3];
idea[4]=timeSpot+idea[3];
priorityQueue.clear();
//c从列表中删除已经在处理的idea
ideaList.remove(idea);
}
}
timeSpot++;
for (int k=0;k<M;k++){
if (status[k]!=0) status[k]--;
}
}
for (int[] idea:ideas){
System.out.println(idea[4]);
}
}
}
题意：多个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));
}
}
}
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
