编程题3

import java.util.*;

public class Main {
    public static void main( String[] args ) {
        Scanner sc = new Scanner( System.in );
        int n = sc.nextInt(), m = sc.nextInt(), p = sc.nextInt();
        Idea[] ideas = new Idea[p];
        Thinker[] thinkers = new Thinker[n];
        Implementor[] implementors = new Implementor[m];
        for( int i = 0; i < m; i ++ )
            impleQueue.push( implementors[i] = new Implementor() );
        for( int i = 0; i < n; i ++ )
            thinkers[i] = new Thinker( i );
        for( int i = 0; i < p; i ++ ) {
            int pm = sc.nextInt()-1;
            int time = sc.nextInt();
            int prio = sc.nextInt();
            int cost = sc.nextInt();
            ideas[i] = new Idea( time, prio, cost );
            events.offer( thinkers[pm].getIdea( ideas[i] ) );
        }
        while( !events.isEmpty() ) {
            int time = events.peek().time;
            do { events.poll().occur();
            } while( !events.isEmpty() && events.peek().time == time );
            while( !impleQueue.isEmpty() && !thinkerQueue.isEmpty() ) {
                Thinker tmp1 = thinkerQueue.poll();
                Implementor tmp2 = impleQueue.pop();
                Idea tmp3 = tmp1.ideaQueue.poll();
                tmp3.finish = time + tmp3.cost;
                events.offer( tmp2.peekIdea( tmp3 ) );
                if( !tmp1.ideaQueue.isEmpty() ) thinkerQueue.offer( tmp1 );
            }
        }
        for( int i = 0; i < p; i ++ )
            System.out.println( ideas[i].finish );
        sc.close();
    }
    static PriorityQueue<Thinker> thinkerQueue = new PriorityQueue<>(
        (Thinker t1,Thinker t2) -> {
            int c1 = t1.ideaQueue.peek().cost;
            int c2 = t2.ideaQueue.peek().cost;
            return c1 == c2 ? t1.order - t2.order : c1 - c2;
        }
    );
    static ArrayDeque<Implementor> impleQueue = new ArrayDeque<>();
    static PriorityQueue<Event> events =
        new PriorityQueue<>( (Event e1,Event e2) -> e1.time - e2.time );
    static class Idea {
        int time, prio, cost, finish;
        Idea( int t, int p, int c ) { time = t; prio = p; cost = c; }
    }
    static class Thinker {
        PriorityQueue<Idea> ideaQueue = new PriorityQueue<>(
            (Idea i1,Idea i2) -> {
                if( i1.prio != i2.prio ) return i2.prio - i1.prio;
                else if( i1.cost != i2.cost ) return i1.cost - i2.cost;
                else return i1.time - i2.time;
            }
        );
        int order;
        Thinker( int o ) { order = o; }
        IdeaEvent getIdea( Idea idea ) {
            return new IdeaEvent( this, idea );
        }
    }
    static class Implementor {
        FinishEvent peekIdea( Idea idea ) {
            return new FinishEvent( this, idea );
        }
    }
    static abstract class Event {
        int time;
        Event( int t ) { time = t; }
        abstract void occur();
    }
    static class IdeaEvent extends Event {
        Thinker thinker;
        Idea idea;
        IdeaEvent( Thinker t, Idea i ) {
            super( i.time );
            thinker = t; idea = i;
        }
        void occur() {
            thinkerQueue.remove( thinker );
            thinker.ideaQueue.offer( idea );
            thinkerQueue.offer( thinker );
        }
    }
    static class FinishEvent extends Event {
        Implementor implementor;
        Idea idea;
        FinishEvent( Implementor imple, Idea i ) {
            super( i.finish );
            implementor = imple; idea = i;
        }
        void occur() {
            impleQueue.push( implementor );
        }
    }
}

java AC 代码

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

const int maxn=3e3+5;

struct Idea
{
    int PMID;      //PM编号
    int startTime; //提出时间
    int priority;  //优先等级
    int costTime;  //所需时间
    int order;     //输入的序号
}idea[maxn];

int n,m,p;
int finishTime[maxn];  //每个Idea的完成时间
int programTime[maxn]; //每个程序员的空闲时刻
vector<Idea> PM_Idea[maxn];  //每个PM未完成的Idea，等待状态

// PM最想实现的Idea优先级
bool cmpPM(Idea a,Idea b)
{
    if(a.priority==b.priority)
    {
        if(a.costTime==b.costTime)
            return a.startTime<b.startTime;
        return a.costTime<b.costTime;
    }
    return a.priority>b.priority;
}

// 程序员挑选Idea的优先级
bool cmpTask(Idea a,Idea b)
{
    if(a.costTime==b.costTime)
        return a.PMID<b.PMID;
    return a.costTime<b.costTime;
}

// 对所有Idea按提出时间从小到大排序
bool cmpTime(Idea a,Idea b)
{
    return a.startTime<b.startTime;
}

int main()
{
    scanf("%d%d%d",&n,&m,&p);
    for(int i=0;i<p;++i)
    {
        scanf("%d%d%d%d",&idea[i].PMID,&idea[i].startTime,&idea[i].priority,&idea[i].costTime);
        idea[i].order=i;
    }

    // 对所有Idea按提出时间从小到大排序
    sort(idea,idea+p,cmpTime);

    // currenTime：当前时间；cnt：完成Idea的数量；pre：上次未加入到等待序列(PM_Idea)中的idea位置
    int currentTime=1,cnt=0,last=0;
    while(cnt<p)
    {
        // 先把在当前时间之前提出的所有Idea加入到等待序列中
        for(int i=last;i<p;++i)
        {
            if(idea[i].startTime==currentTime)
            {
                int PMID=idea[i].PMID;
                PM_Idea[PMID].push_back(idea[i]); //加入等待序列
                sort(PM_Idea[PMID].begin(),PM_Idea[PMID].end(),cmpPM); //更新序列中Idea的顺序
                
                //进行到最后一个Idea时更新一下last的值
                if(i==p-1)
                    last=p;
            }
            else
            {
                last=i; //记录将要被提出的Idea的位置，下一次可以直接从此位置开始判断添加
                break;
            }
        }

        vector<Idea> wait_Idea; //程序员要选择的Idea序列
        // 为每个PM添加最想要完成的Idea
        for(int i=1;i<=n;++i)
            if(!PM_Idea[i].empty())
                wait_Idea.push_back(PM_Idea[i][0]);

        for(int i=0;i<m;++i)
        {
            // 如果当前程序员处于空闲状态，并且等待序列不为空的话
            if(programTime[i]<=currentTime&&!wait_Idea.empty())
            {
                // 对等待序列进行排序，使得优先级高的Idea排在最前面
                sort(wait_Idea.begin(),wait_Idea.end(),cmpTask);
                // 更新当前程序员的空闲时间
                programTime[i]=currentTime+wait_Idea[0].costTime;
                // 记录Idea的完成时间
                finishTime[wait_Idea[0].order]=programTime[i];
                
                int PMID=wait_Idea[0].PMID;
                // 从等待序列中将这个Idea删除
                PM_Idea[PMID].erase(PM_Idea[PMID].begin());
                // 从选择序列中将这个Idea删除
                wait_Idea.erase(wait_Idea.begin());
                // 更新选择序列，添加这个PM下一个想要完成的Idea
                if(!PM_Idea[PMID].empty())
                    wait_Idea.push_back(PM_Idea[PMID][0]);
                
                ++cnt;
            }
        }
        ++currentTime;
    }

    for(int i=0;i<p;++i)
        printf("%d\n",finishTime[i]);
    return 0;
}

这个题不难，思路十分容易想，问题是，要足够信心和耐心。

看过来~~~

这个题的描述不是很容易让人看懂，我也是看着执行的预期输出反着推题干所表述的含义，将题目梳理并补充如下

思路

• 有N个PM项目经理在时间轴上的不同时刻给 M个程序员提idea需求，idea拥有序号、优先级、提出时间、所需时间的属性。PM有多个需求的时候先自己PK，选出认为最优先的丢给程序员去做，在众多PM中，程序员资源优先也只能从所有PM过滤完的需求再次选所需时间最短的来做。
• 大前提是程序员不知道未来时间的需求，不会做未来的idea需求，也就是只会从当前时刻以前的需求中进行挑选
• 如果当前时间一个PM已经有多个idea需求提出，那么PM只能选出一个最优先的（题干描述的很隐蔽，这条是关键）
• 给定的数据中，所有需求按时间顺序排序，每次处理时大于当前时间的过滤掉，小于当前时间的都有可能去处理
• 过滤掉时间条件后，按照每个PM的各自的需求，各自排序（这道题的核心坑点就在这，读题目容易误解，如果每个PM不将自己的需求排好序选出一个出来，而是将所有的需求都丢给程序员，程序员自身理解的优先级规则，是按照所需时间多少来做的，那么一个PM的两个需求就有可能程序员先做时间少但优先级低的）
• 所有PM都将自己最优先的需求列出后，程序员再从这个集合中选出要做的，没来得及做的需求会参与到下次比较中，下次比较有可能又被新的需求更高的优先级替代掉。

具体操作

• 比较器
  • 时间顺序比较器
  • PM理解的优先级比较器
  • Programmer理解的优先级比较器
• 集合
  1) 所有idea的集合
  2) 通过所有idea的集合过滤出小于当前时间的
  3) 从2中得出的按照PM各自选出最优先的得出新的集合
  4) 空闲的程序员从3中的集合，选出程序员理解的做先做的任务去做，剩余的任务将参与下一次第3步骤的比较

写了好几个小时才对，挺绕的，看别人说这个题简单，可能是我太笨了。我要面试时写，肯定写不出来，题目都不一定能读明白。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef struct Task {
    int belong;
    int start;
    int priority;
    int need_time;
    int number;
    int end;
}Task;
Task A[3000], *B[3000];
int n, m, p;
class cmp {
    public:
        bool operator()(const Task *a, const Task* b) {
            return a->priority == b->priority ? (a->need_time == b->need_time? a->start > b->start : a->need_time > b->need_time) : a->priority priority;
        }
};
void solve() {
    // m 程序员
    priority_queue, greater> T;
    for(int i = 0; i < m; ++i) {
        T.push(0);
    }
    // p 对idea 进行排序
    sort(B, B+p, [](const Task* a, const Task* b) {
        return a->start start;
    });
    // 等待完成的idea
    int cnt = 0, idx = 0;
    priority_queue, cmp> ID[n+1];
    for(int i = 0; i < p; ++i) {
        int t = T.top();
        T.pop();
        while(idx start <= t) {
            ID[B[idx]->belong].push(B[idx]);
            ++idx;
            ++cnt;
        }
        if(cnt == 0) {
            Task * x = B[idx++];
            ID[x->belong].push(x);
            ++cnt;
            while(idx start == x->start) {
                ID[B[idx]->belong].push(B[idx]);
                ++idx;
                ++cnt;
            } 
        }
        int min_time = INT_MAX, iidx = -1;
        for(int i = 1; i <= n; ++i) {
            if(ID[i].size() > 0 && ID[i].top()->need_time < min_time) {
                min_time = ID[i].top()->need_time;
                iidx = i;
            }
        }
        Task * z = ID[iidx].top();
        t = max(t, z->start) + z->need_time;
        A[z->number].end = t;
        T.push(t);
        ID[iidx].pop();
        --cnt;
    }
    for(int i = 0; i < p; ++i) {
        printf("%d\n", A[i].end);
    }
}
int main() {
    scanf("%d%d%d", &n, &m, &p);
    for(int i = 0; i  < p; ++i) {
        scanf("%d%d%d%d",&A[i].belong, &A[i].start, &A[i].priority, &A[i].need_time);
        A[i].number = i;
        B[i] = &A[i];
    }
    solve();
}

data = input()
m = int(data.split()[1])
p = int(data.split()[2])
employee = []
i = 0
time = 0
ideas = []
best_ideas = []
ideas_q = []
while p > i:
    s = input()
    ideas.append([int(s.split()[0]), int(s.split()[1]), int(s.split()[2]), int(s.split()[3])])
    i += 1
for j in ideas:
    a = True
    for k in ideas_q:
        if j[0] == k[0][0]:
            k.append(j)
            a = False
    if a:
        ideas_q.append([j])

i = 0
while m > i:
    employee.append([0])
    i += 1

while p > 0:
    time += 1
    max = []
    for i in employee:
        if i[0] != 0:
            i[0] -= 1
    while [0] in employee and p > 0:
        for j in ideas_q:
            a = False
            for k in j:
                if k.__len__() != 5 and time >= k[1]:
                    max = k
                    a = True
                    break
            for k in j:
                if k.__len__() != 5 and time >= k[1]:
                    if k[2] >= max[2]:
                        if max[2] != k[2]:
                            max = k
                        elif max[3] >= k[3]:
                            if max[3] != k[3]:
                                max = k
                            elif max[1] > k[1]:
                                max = k
            if a:
                best_ideas.append(max)
        max = best_ideas[0]
        for k in best_ideas:
            if max[3] >= k[3]:
                if max[3] != k[3]:
                    max = k
                elif max[0] > k[0]:
                    max = k
        max.append((time + max[3]))
        p -= 1
        for i in employee:
            if i == [0]:
                i[0] += max[3]
                break
        best_ideas.clear()

for i in ideas:
    print(i[4])

	

看题看了半天，我们先捋一捋。
首先重要的是idea，每个idea都包含了
1.对应PM的id 2.提出时间 3.优先级 4.需要的时间
2.对于PM来说，他们产生idea，PM有自己的规则来选择最想完成的idea。
3.对于程序员，首先要看自己是否有空，然后根据此时的所有PM最想完成的idea，
根据自己的规则选取idea来做，同时更新对应程序员的空闲时刻。
这里面有个十分重要的变量就是时间，对于时间的控制一定要注意。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct idea{
    int PM_id;
    int post_time;
    int priority;
    int cost_time;
    int order; //  idea 序号
}ideas[3001];

int N,M,P;
int finish_time[3001];//完成每个idea的时间
int program_time[3001];//程序员空闲时刻
vector<idea> PM_idea[3001];//每个PM某时刻所拥有的未完成的idea

 bool cmp_post(const idea &a,const idea &b){
     return a.post_time<b.post_time;
 }
 //PM的排序
bool cmp_priority(const idea &a,const idea &b){
    if(a.priority!=b.priority)
        return a.priority>b.priority;
    else if(a.cost_time!=b.cost_time)
        return a.cost_time<b.cost_time;
    return a.post_time<b.post_time;
}
//程序员的排序
bool cmp_cost(const idea &a,const idea &b){
    if(a.cost_time!=b.cost_time)
        return a.cost_time<b.cost_time;
    return a.PM_id<b.PM_id;
}

int main(){
    cin>>N>>M>>P;
    int pm,post,por,cos;
    for(int i = 0;i<P;i++){
        cin>>pm>>post>>por>>cos;
        ideas[i] = {pm-1,post,por,cos,i};
    }
    sort(ideas,ideas+P,cmp_post);//按照时间排序
    int nowtime = 1,cnt = 0,last = 0;//nowtime 当前时间 cnt已完成任务 last下一次添加任务的起点
    while(cnt<P){

        for(int i = last;i<P;i++){
            if(ideas[i].post_time==nowtime){
                //个对应的PM添加这个idea，再根据PM判断规则排序
                PM_idea[ideas[i].PM_id].push_back(ideas[i]);
                sort(PM_idea[ideas[i].PM_id].begin(),PM_idea[ideas[i].PM_id].end(),cmp_priority);
                if(i==P-1)
                    last = P;
            }else{
                last = i;
                break;
            }
        }
        //选取每个PM最想完成的idea
        vector<idea>PM_pro;
        for(int i =0;i<N;i++){
            if(!PM_idea[i].empty()){
                PM_pro.push_back(PM_idea[i][0]);
            }
        }

        for(int i = 0;i<M;i++){
            //程序员i空闲并且此时有idea
            if(program_time[i]<=nowtime&&!PM_pro.empty()){
                //按照程序员的规则来排序
                sort(PM_pro.begin(),PM_pro.end(),cmp_cost);
                program_time[i] = nowtime+PM_pro[0].cost_time;
                finish_time[PM_pro[0].order] = program_time[i];
                PM_idea[PM_pro[0].PM_id].erase(PM_idea[PM_pro[0].PM_id].begin());
                if(!PM_idea[PM_pro[0].PM_id].empty())
                    PM_pro.push_back(PM_idea[PM_pro[0].PM_id][0]);
                PM_pro.erase(PM_pro.begin());
                cnt++;
            }
        }
        nowtime++;
    }
    for(int i = 0;i<P;i++){
        cout<<finish_time[i]<<endl;
    }
    return 0;
}