题解 | 编程题3

#include <bits/stdc++.h>
using namespace std;

struct Idea {
    int id;         // 原始序号
    int pmId;       // PM序号
    int time;       // 提出时间
    int priority;   // 优先级
    int duration;   // 所需时间
    
    Idea(int id, int pmId, int time, int priority, int duration) 
        : id(id), pmId(pmId), time(time), priority(priority), duration(duration) {}
};

class Programmer {
private:
    int currentTime;
    
    Idea* selectBestIdea(vector<Idea*>& ideas, int pmCount) {
        vector<Idea*> pmTopIdeas(pmCount, nullptr);
        
        // 找出每个PM最优先的idea
        for (auto idea : ideas) {
            if (currentTime < idea->time) continue;
            
            int pmIndex = idea->pmId - 1;
            if (!pmTopIdeas[pmIndex] || 
                idea->priority > pmTopIdeas[pmIndex]->priority ||
                (idea->priority == pmTopIdeas[pmIndex]->priority && 
                 idea->duration < pmTopIdeas[pmIndex]->duration) ||
                (idea->priority == pmTopIdeas[pmIndex]->priority && 
                 idea->duration == pmTopIdeas[pmIndex]->duration && 
                 idea->time < pmTopIdeas[pmIndex]->time)) {
                pmTopIdeas[pmIndex] = idea;
            }
        }
        
        // 从所有PM的最优idea中选择一个
        Idea* bestIdea = nullptr;
        for (auto idea : pmTopIdeas) {
            if (!idea) continue;
            if (!bestIdea || 
                idea->duration < bestIdea->duration ||
                (idea->duration == bestIdea->duration && 
                 idea->pmId < bestIdea->pmId)) {
                bestIdea = idea;
            }
        }
        
        return bestIdea;
    }
    
public:
    Programmer() : currentTime(1) {}
    
    int getTime() const { return currentTime; }
    
    int processIdea(vector<Idea*>& ideas, int pmCount) {
        Idea* selectedIdea = selectBestIdea(ideas, pmCount);
        
        if (selectedIdea) {
            int ideaId = selectedIdea->id;
            currentTime += selectedIdea->duration;
            
            // 移除已处理的idea
            auto it = find(ideas.begin(), ideas.end(), selectedIdea);
            if (it != ideas.end()) {
                ideas.erase(it);
            }
            
            return ideaId;
        }
        
        currentTime++;
        return -1;
    }
};

class Solution {
public:
    vector<int> solve(int n, int m, int p, vector<vector<int>>& ideaInfo) {
        vector<int> result(p);
        vector<Idea*> ideas;
        priority_queue<pair<int, Programmer*>, 
                      vector<pair<int, Programmer*>>,
                      greater<>> programmers;
        
        // 初始化ideas
        for (int i = 0; i < p; i++) {
            ideas.push_back(new Idea(i, ideaInfo[i][0], ideaInfo[i][1], 
                                   ideaInfo[i][2], ideaInfo[i][3]));
        }
        
        // 初始化programmers
        for (int i = 0; i < m; i++) {
            programmers.push({1, new Programmer()});
        }
        
        // 处理所有idea
        while (!ideas.empty()) {
            auto [time, programmer] = programmers.top();
            programmers.pop();
            
            int ideaId = programmer->processIdea(ideas, n);
            if (ideaId != -1) {
                result[ideaId] = programmer->getTime();
            }
            
            programmers.push({programmer->getTime(), programmer});
        }
        
        // 清理内存
        while (!programmers.empty()) {
            delete programmers.top().second;
            programmers.pop();
        }
        
        return result;
    }
};

int main() {
    int n, m, p;
    cin >> n >> m >> p;
    
    vector<vector<int>> ideaInfo(p, vector<int>(4));
    for (int i = 0; i < p; i++) {
        for (int j = 0; j < 4; j++) {
            cin >> ideaInfo[i][j];
        }
    }
    
    Solution solution;
    vector<int> result = solution.solve(n, m, p, ideaInfo);
    
    for (int time : result) {
        cout << time << endl;
    }
    
    return 0;
}

import java.util.*;

public class Main {
    static class Idea {
        final int id;
        final int pmId;
        final int time;
        final int priority;
        final int duration;
        
        Idea(int id, int pmId, int time, int priority, int duration) {
            this.id = id;
            this.pmId = pmId;
            this.time = time;
            this.priority = priority;
            this.duration = duration;
        }
    }
    
    static class Programmer {
        private int currentTime;
        
        Programmer() {
            this.currentTime = 1;
        }
        
        private Idea selectBestIdea(List<Idea> ideas, int pmCount) {
            Idea[] pmTopIdeas = new Idea[pmCount];
            
            // 找出每个PM最优先的idea
            for (Idea idea : ideas) {
                if (currentTime < idea.time) continue;
                
                int pmIndex = idea.pmId - 1;
                Idea currentTop = pmTopIdeas[pmIndex];
                
                if (currentTop == null || 
                    idea.priority > currentTop.priority ||
                    (idea.priority == currentTop.priority && 
                     idea.duration < currentTop.duration) ||
                    (idea.priority == currentTop.priority && 
                     idea.duration == currentTop.duration && 
                     idea.time < currentTop.time)) {
                    pmTopIdeas[pmIndex] = idea;
                }
            }
            
            // 从所有PM的最优idea中选择一个
            Idea bestIdea = null;
            for (Idea idea : pmTopIdeas) {
                if (idea == null) continue;
                if (bestIdea == null || 
                    idea.duration < bestIdea.duration ||
                    (idea.duration == bestIdea.duration && 
                     idea.pmId < bestIdea.pmId)) {
                    bestIdea = idea;
                }
            }
            
            return bestIdea;
        }
        
        public int getTime() {
            return currentTime;
        }
        
        public int processIdea(List<Idea> ideas, int pmCount) {
            Idea selectedIdea = selectBestIdea(ideas, pmCount);
            
            if (selectedIdea != null) {
                int ideaId = selectedIdea.id;
                currentTime += selectedIdea.duration;
                ideas.remove(selectedIdea);
                return ideaId;
            }
            
            currentTime++;
            return -1;
        }
    }
    
    static class Solution {
        public int[] solve(int n, int m, int p, int[][] ideaInfo) {
            int[] result = new int[p];
            List<Idea> ideas = new ArrayList<>();
            
            // 初始化ideas
            for (int i = 0; i < p; i++) {
                ideas.add(new Idea(i, ideaInfo[i][0], ideaInfo[i][1], 
                                 ideaInfo[i][2], ideaInfo[i][3]));
            }
            
            // 使用优先队列管理程序员
            PriorityQueue<Programmer> programmers = new PriorityQueue<>(
                (a, b) -> a.getTime() - b.getTime()
            );
            
            for (int i = 0; i < m; i++) {
                programmers.offer(new Programmer());
            }
            
            while (!ideas.isEmpty()) {
                Programmer programmer = programmers.poll();
                int ideaId = programmer.processIdea(ideas, n);
                
                if (ideaId != -1) {
                    result[ideaId] = programmer.getTime();
                }
                
                programmers.offer(programmer);
            }
            
            return result;
        }
    }
    
    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[][] ideaInfo = new int[p][4];
        for (int i = 0; i < p; i++) {
            for (int j = 0; j < 4; j++) {
                ideaInfo[i][j] = sc.nextInt();
            }
        }
        
        Solution solution = new Solution();
        int[] result = solution.solve(n, m, p, ideaInfo);
        
        for (int time : result) {
            System.out.println(time);
        }
        
        sc.close();
    }
}

from typing import List, Optional
import heapq

class Idea:
    def __init__(self, id: int, pm_id: int, time: int, priority: int, duration: int):
        self.id = id            # 原始序号
        self.pm_id = pm_id      # PM序号
        self.time = time        # 提出时间
        self.priority = priority # 优先级
        self.duration = duration # 所需时间

class Programmer:
    def __init__(self):
        self.current_time = 1
        
    def select_best_idea(self, ideas: List[Idea], pm_count: int) -> Optional[Idea]:
        # 找出每个PM最优先的idea
        pm_top_ideas = [None] * pm_count
        
        for idea in ideas:
            if self.current_time < idea.time:
                continue
                
            pm_idx = idea.pm_id - 1
            curr_idea = pm_top_ideas[pm_idx]
            
            if (not curr_idea or 
                idea.priority > curr_idea.priority or
                (idea.priority == curr_idea.priority and 
                 idea.duration < curr_idea.duration) or
                (idea.priority == curr_idea.priority and 
                 idea.duration == curr_idea.duration and 
                 idea.time < curr_idea.time)):
                pm_top_ideas[pm_idx] = idea
        
        # 从所有PM的最优idea中选择一个
        best_idea = None
        for idea in pm_top_ideas:
            if not idea:
                continue
            if (not best_idea or 
                idea.duration < best_idea.duration or
                (idea.duration == best_idea.duration and 
                 idea.pm_id < best_idea.pm_id)):
                best_idea = idea
                
        return best_idea
    
    def process_idea(self, ideas: List[Idea], pm_count: int) -> int:
        selected_idea = self.select_best_idea(ideas, pm_count)
        
        if selected_idea:
            idea_id = selected_idea.id
            self.current_time += selected_idea.duration
            ideas.remove(selected_idea)
            return idea_id
            
        self.current_time += 1
        return -1

class Solution:
    def solve(self, n: int, m: int, p: int, idea_info: List[List[int]]) -> List[int]:
        result = [0] * p
        ideas = []
        for i, info in enumerate(idea_info):
            ideas.append(Idea(i, info[0], info[1], info[2], info[3]))
        
        # 使用优先队列管理程序员
        programmers = [(1, i, Programmer()) for i in range(m)]
        heapq.heapify(programmers)
        
        while ideas:
            time, idx, programmer = heapq.heappop(programmers)
            idea_id = programmer.process_idea(ideas, n)
            
            if idea_id != -1:
                result[idea_id] = programmer.current_time
                
            heapq.heappush(programmers, 
                          (programmer.current_time, idx, programmer))
            
        return result

# 读取输入
n, m, p = map(int, input().split())
idea_info = []
for _ in range(p):
    idea_info.append(list(map(int, input().split())))

solution = Solution()
result = solution.solve(n, m, p, idea_info)

for time in result:
    print(time)