题解 | #编程题3#

import java.util.*;

public class Main {
    private static int pmNum;
    
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        
        pmNum = in.nextInt();
        int programmerNum = in.nextInt();
        int ideaNum = in.nextInt();
        
        ArrayList<Idea> ideaList = new ArrayList<>(ideaNum);
        for(int i=0; i<ideaNum; i++){
            ideaList.add(new Idea(i, in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt()));
        }
        
        // 小根堆
        PriorityQueue<Programmer> programmerQueue = new PriorityQueue<>(programmerNum, Comparator.comparingInt(o -> o.timeCurr));
        for(int i=0; i<programmerNum; i++){
            programmerQueue.add(new Programmer(1));
        }
        
        int[] result = new int[ideaNum];
        while(!ideaList.isEmpty()){
            Programmer programmer = programmerQueue.remove();
            int seq = programmer.handle(ideaList);
            if(seq != -1){
                result[seq] = programmer.timeCurr;
            }
            programmerQueue.add(programmer);
        }
        
        for(int time: result){
            System.out.println(time);
        }
    }

    private static class Idea{
        int seq;
        int pmSeq;
        int timeSubmit;
        int priority;
        int duration;

        public Idea(int seq, int pmSeq, int timeSubmit, int priority, int duration){
            this.seq = seq;
            this.pmSeq = pmSeq;
            this.timeSubmit = timeSubmit;
            this.priority = priority;
            this.duration = duration;
        }
    }

    private static class Programmer{
        int timeCurr;

        public Programmer(int timeCurr){
            this.timeCurr = timeCurr;
        }

        private Idea selectIdea(List<Idea> ideaList){
            Idea[] topIdeaOfPms = new Idea[pmNum+1];
            // 选出每个PM最想完成的idea
            for(Idea idea : ideaList){
                // 当前programmer所处时间 < 当前idea提交时间
                if(this.timeCurr < idea.timeSubmit){
                    continue;
                }
                if(topIdeaOfPms[idea.pmSeq] == null){
                    topIdeaOfPms[idea.pmSeq] = idea;
                    continue;
                }

                // 优先等级
                if(idea.priority < topIdeaOfPms[idea.pmSeq].priority){
                    continue;
                }
                if(idea.priority > topIdeaOfPms[idea.pmSeq].priority){
                    topIdeaOfPms[idea.pmSeq] = idea;
                    continue;
                }

                // 所需时间
                if(idea.duration < topIdeaOfPms[idea.pmSeq].duration){
                    topIdeaOfPms[idea.pmSeq] = idea;
                    continue;
                }
                if(idea.duration > topIdeaOfPms[idea.pmSeq].duration){
                    continue;
                }

                // 提交时间
                if(idea.timeSubmit < topIdeaOfPms[idea.pmSeq].timeSubmit){
                    topIdeaOfPms[idea.pmSeq] = idea;
                    continue;
                }
                if(idea.timeSubmit > topIdeaOfPms[idea.pmSeq].timeSubmit){
                    continue;
                }
            }

            // 该程序员最终选择的idea
            Idea selectedIdea = null;
            for(Idea idea : topIdeaOfPms){
                if(idea == null){
                    continue;
                }
                if(selectedIdea == null){
                    selectedIdea = idea;
                }

                // 所需时间
                if(idea.duration < selectedIdea.duration){
                    selectedIdea = idea;
                }
                // PM序号
                else if(idea.duration==selectedIdea.duration && idea.pmSeq<selectedIdea.pmSeq){
                    selectedIdea = idea;
                }
            }
            return selectedIdea;
        }

        private int handle(List<Idea> ideaList){
            Idea selectedIdea = this.selectIdea(ideaList);
            if(selectedIdea != null){
                timeCurr += selectedIdea.duration;
                ideaList.remove(selectedIdea);
                return selectedIdea.seq;
            }else{
                // 未获取到需求
                timeCurr += 1;
                return -1;
            }
        }
    }
}