产品经理(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序号、提出时间、优先等级和所需时间。
所有输入数据范围为 [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
同时有M个程序员，每个程序员空闲的时候就会查看每个PM尚未执行并且最想完成的一个idea,然后从中挑选出所需时间最小的一个idea独立实现，如果所需时间相同则选择PM序号最小的。直到完成了idea才会重复上述操作。如果有多个同时处于空闲状态的程序员，那么他们会依次进行查看idea的操作。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
public class Main {
static class Program {
int id;
int pmId;
int priority;
int processTime;
int comeUpTime;
public Program(int id, int pmId, int priority, int processTime, int comeUpTime) {
this.id = id;
this.pmId = pmId;
this.priority = priority;
this.processTime = processTime;
this.comeUpTime = comeUpTime;
}
}
static class PMComparator implements Comparator<Program> {
@Override
public int compare(Program o1, Program o2) {
if (o1.priority != o2.priority) {
return o2.priority - o1.priority;
} else if (o1.processTime != o2.processTime) {
return o1.processTime - o2.processTime;
} else {
return o1.comeUpTime - o2.comeUpTime;
}
}
}
static class PComparator implements Comparator<Program> {
@Override
public int compare(Program o1, Program o2) {
if (o1.processTime != o2.processTime) {
return o1.processTime - o2.processTime;
} else {
return o1.pmId - o2.pmId;
}
}
}
static class BigQueue {
List<PriorityQueue<Program>> pmQueue;
// 程序员堆
Program[] programs;
int heapSize;
// 建立pmId与程序员堆位置的映射
int[] indices;
// 程序员堆比较器
PComparator comparator;
public BigQueue(int pmSize) {
pmQueue = new ArrayList<>();
for (int i = 0; i <= pmSize; ++i) {
pmQueue.add(new PriorityQueue<>(new PMComparator()));
}
programs = new Program[pmSize];
heapSize = 0;
indices = new int[pmSize + 1];
for (int i = 0; i <= pmSize; ++i) {
indices[i] = -1;
}
comparator = new PComparator();
}
public void swap(int a, int b) {
Program pa = programs[a];
Program pb = programs[b];
programs[a] = pb;
programs[b] = pa;
indices[pa.pmId] = b;
indices[pb.pmId] = a;
}
public void heapInsert(int index) {
while (index > 0) {
int parent = (index - 1) / 2;
if (comparator.compare(programs[index], programs[parent]) < 0) {
swap(index, parent);
index = parent;
} else {
break;
}
}
}
public void heapify(int index) {
while (index < heapSize) {
int left = 2 * index + 1;
int right = 2 * index + 2;
int best = index;
if (left < heapSize && comparator.compare(programs[left], programs[best]) < 0) {
best = left;
}
if (right < heapSize && comparator.compare(programs[right], programs[best]) < 0) {
best = right;
}
if (best == index) {
break;
}
swap(index, best);
index = best;
}
}
public void add(Program p) {
// 首先得将其添加到产品经理堆中
PriorityQueue<Program> queue = pmQueue.get(p.pmId);
queue.add(p);
Program head = queue.peek();
// 然后判断该项目经理提交给程序员的项目是否需要替换
int index = indices[head.pmId];
if (index == -1) {
// 还没有提交过项目
programs[heapSize] = head;
indices[head.pmId] = heapSize;
heapInsert(heapSize++);
} else {
// 已经提交过项目了
programs[index] = head;
heapInsert(index);
heapify(index);
}
}
public Program pop() {
// 从程序员堆中弹出一个任务
Program head = programs[0];
// 从产品经理中弹出该任务
PriorityQueue<Program> queue = pmQueue.get(head.pmId);
queue.poll();
// 产品经理堆为空
if (queue.isEmpty()) {
swap(0, heapSize - 1);
programs[--heapSize] = null;
indices[head.pmId] = -1;
heapify(0);
} else {
// 不为空，将该项目经理的后一个项目添加到程序员堆中
programs[0] = queue.peek();
heapify(0);
}
return head;
}
public boolean isEmpty() {
return heapSize == 0;
}
}
static int[] process(PriorityQueue<Program> startQue, int p, int n, int m) {
int[] ans = new int[p];
BigQueue bigQueue = new BigQueue(n);
// 程序员唤醒时机
PriorityQueue<Integer> wakeup = new PriorityQueue<>();
for (int i = 0; i < m; ++i) {
wakeup.add(1);
}
int i = 0;
while (i < p) {
int time = wakeup.poll();
while (!startQue.isEmpty()) {
if (startQue.peek().comeUpTime <= time) {
bigQueue.add(startQue.poll());
} else {
break;
}
}
if (bigQueue.isEmpty()) {
// 程序员醒来的时间太早了
wakeup.add(startQue.peek().comeUpTime);
} else {
// 执行任务
Program program = bigQueue.pop();
ans[program.id] = time + program.processTime;
wakeup.add(ans[program.id]);
++i;
}
}
return ans;
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String s = reader.readLine();
String[] strings = s.split(" ");
// n个项目经理
int n = Integer.parseInt(strings[0]);
// m个程序员
int m = Integer.parseInt(strings[1]);
// p个项目
int p = Integer.parseInt(strings[2]);
// 按照项目提出时间顺序进排列
PriorityQueue<Program> startQue = new PriorityQueue<>(new Comparator<Program>() {
@Override
public int compare(Program o1, Program o2) {
return o1.comeUpTime - o2.comeUpTime;
}
});
for (int i = 0; i < p; ++i) {
s = reader.readLine();
strings = s.split(" ");
int pmId = Integer.parseInt(strings[0]);
// 牛客的bug,需要获得最大的pmId才可以，不然数组会越界
n = Math.max(n, pmId);
int comeUpTime = Integer.parseInt(strings[1]);
int priority = Integer.parseInt(strings[2]);
int processTime = Integer.parseInt(strings[3]);
startQue.add(new Program(i, pmId, priority, processTime, comeUpTime));
}
int[] ans = process(startQue, p, n, m);
for (int v : ans) {
System.out.println(v);
}
}
}
N,M,P = [int(a) for a in input().split()]
Ideas = {}
for i in range(P):
X = [int(a) for a in input().split()]
Ideas[X[0]] = Ideas.get(X[0],[]) + [[i]+X[1:]]
for k,v in Ideas.items():
v.sort(key=lambda x:(-x[2],x[3],x[1]))
Ideas[k]=v
def Select(t):
a,b,c = 0,0,9999
for k in Ideas.keys():
for j in range(len(Ideas[k])):
if Ideas[k][j][1]<=t:
if Ideas[k][j][3]<c&nbs***bsp;(Ideas[k][j][3]==c and k<a):
a,b,c = k,j,Ideas[k][j][3]
break
idx = -1
if a>0:
idx = Ideas[a][b][0]
Ideas[a] = Ideas[a][:b]+Ideas[a][b+1:]
return idx,c
result = [0]*P
CXY = [0]*M
t,count = 1,0
while count<P:
flag = 0
for i in range(M):
if CXY[i]==0:
idx,c = Select(t)
if idx<0:
flag=1
break
result[idx] = t+c
CXY[i]=c
count += 1
if flag>0:
t += 1
CXY = [c-1 if c>0 else 0 for c in CXY]
else:
m = min(CXY)
t += m
CXY = [c-m for x in CXY]
for r in result:
print(r)
import java.util.Arrays;
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int P = sc.nextInt();
int[][] arr = new int[P][5];
for(int i=0;i<P;i++){
for(int j =0;j<4;j++){
arr[i][j]=sc.nextInt();
}
arr[i][4]=i;
}
Arrays.sort(arr,(a,b)->{
if(a[1]!=b[1])return a[1]-b[1];
if(a[2]!=b[2])return a[2]-b[2];
if(a[3]!=b[3])return a[3]-b[3];
return a[0]-b[0];
});
int[] res = solve(arr,M);
for(int i=0;i<P;i++){
System.out.println(res[i]);
}
}
public static int[] solve(int[][] arr, int M){
int time = arr[0][1];
int index = 0;
int[] res = new int[arr.length];
int[] numM = new int[M];
Arrays.fill(numM,time);
while(index<arr.length){
for(int i=0;i<M;i++){
if(numM[i]==time){
int t = time+arr[index][3];
res[arr[index][4]] = t;
numM[i] = t;
index++;
}
}
int min = 0x7fffffff;
for(int i=0;i<M;i++){
if(numM[i]<min)min=numM[i];
}
time=min;
}
return res;
}
} 
// 过不了。没整明白啥原因。有大佬帮忙看看嘛
import java.util.*;
public class Main{
public static void main(String[] args){
int n,m,p;
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
p = scan.nextInt();
String s = scan.nextLine();
// 增加一个字段用于记录任务的序号
int idx = 1;
// 每个任务的提出者id 提出时间 优先级 所需时间
int pm,occur,priori,cost;
// 保存所给的所有任务
ArrayList<Task> array = new ArrayList<>();
for(int i=0;i<p;++i){
String[] line = scan.nextLine().split(" ");
pm = Integer.parseInt(line[0]);
occur = Integer.parseInt(line[1]);
priori = Integer.parseInt(line[2]);
cost = Integer.parseInt(line[3]);
array.add(new Task(idx++,pm,occur,priori,cost));
}
// 每个PM都维护一个优先队列
PriorityQueue<Task>[] pq = new PriorityQueue[n+1];
// 记录每个程序员还要忙多长时间，0表示空闲
int[] busy = new int[m];
// 题目要求的每个任务的完成时间
int[] ans = new int[p+1];
// 初始时刻
int time = 0;
// 只要仍有任务待完成就一直搜索
while(p>0){
// 时间增加
++time;
// 在忙的程序员忙碌时间减1
for(int i=0;i<m;++i){
if(busy[i]>0){
busy[i] -= 1;
}
}
// 把属于当前时刻想出来的idea加到相应的PM的队列中
for(int i=0;i<array.size();++i){
if(array.get(i).occur==time){
int p_id = array.get(i).pm;
if(pq[p_id]==null)
pq[p_id] = new PriorityQueue<Task>();
pq[p_id].offer(array.get(i));
}
}
// 配置好了所有idea后，程序员开始做选择
for(int i=0;i<m;++i){
// 发现一个空闲的程序员
if(busy[i]==0){
// 仍有任务未完成
if(p>0){
// 被该程序员领走一个任务
--p;
// 程序员依次查询每个PM队列，
// 按时间代价、PM序号做优先级进行比较，选择任务
int fee = Integer.MAX_VALUE;
int pm_idx = Integer.MAX_VALUE;
for(int j=1;j<pq.length;++j){
if(pq[j]!=null && !pq[j].isEmpty()){
Task t = pq[j].peek();
if(t.cost<=fee){
fee = t.cost;
if(t.pm<pm_idx)
pm_idx = t.pm;
}
}
}
// 程序员进行一圈的比较后 选择好了想做的任务
Task tmp = pq[pm_idx].poll();
// 记录该任务的完成时间
ans[tmp.id] = time + tmp.cost;
// 重置忙碌时间为该任务所需时间
busy[i] = tmp.cost;
}
// 否则跳出
else break;
}
}
}
for(int i=1;i<ans.length;++i)
System.out.println(ans[i]);
}
// 每个PM队列中的任务
static class Task implements Comparable{
public int id,pm,occur,priori,cost;
public Task(int id,int pm,int occur,int priori,int cost){
this.id = id;
this.pm = pm;
this.occur = occur;
this.priori = priori;
this.cost = cost;
}
// 依次按优先级 所需时间 提出时间 进行比较
@Override
public int compareTo(Object o){
Task t = (Task)o;
if(this.priori!=t.priori)
return t.priori-this.priori;
else if(this.cost!=t.cost)
return this.cost-t.cost;
return this.occur-t.occur;
}
}
}
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
