字节跳动2018年试题:实现PM的idea

链接：https://www.nowcoder.com/questionTerminal/f76b7bc64e554edaa53d8e0d84f921c5?f=discussion
来源：牛客网

题目的表述非常绕.仔细阅读并尝试理解题意.

我们应该为每个PM保持1个priority_queue,保存当前已经被提出来的idea.注意,程序员只能看到他的首个idea(程序员眼中的优先排名准则与pm不同!)

开一个完成时间的数组time_of_idea_completed记录每个idea的完成时间.

开一个数组time_to_finish_current_idea,其中time_to_finish_current_idea[i]的含义为编号为i(从1开始编号)的程序员手头上的idea还要处理多久.

设置一个变量current_time来保存当前时间

设置一个变量num_of_ideas_left记录当前时间点还有多少idea没有被分配给程序员.进入主循环的条件是还有任务没有被分配(一旦任务都被分配,就可以确定它们在什么时间被完成,就不需要继续模拟了)

传入的参数ideas按照时间升序排列(按照降序排列然后从尾部移出效率更高,但是没那么直观.本题数据规模不大,这样也可以通过)

另外设置一个

vector<priority_queue<idea> >ideas_has_been_proposed_group_by_pm,按照下标保存每个pm当前时间点已经提出的idea并且按照pm的优先级排名排成一个优先队列.C++的优先队列默认是大顶堆,即top()返回最大元,与Java相反.</idea>

进入主循环之后时间+1.我们考虑什么东西需要更新:可能有一些idea被提出来(判断条件为提出idea的时间<=current_time)我们将这些idea从ideas移出并加入对应的pm的优先队列中

开一个vector保存所有的”pm眼中的最重要idea”.(可能有一些pm的所有idea都已经被分配了那么他的队列为空)

新建一个临时vector保存每个pm眼中优先级最高的idea.注意,这个vector需要按照程序员的标准进行排序.

循环考虑每个程序员的变化.他手头上的idea剩余处理时间-1.一旦这个时间为0,表明他可以接手下一个idea.如果temp不为空那么他确实需要接手一个idea(可能出现空闲但是无事可做的情况,比如所有的idea都是时间10以后提出的.)

然后每次程序员按照程序员的标准找优先级最高的idea,就是temp[0]并接手.一旦一个idea被程序猿选中,从这个临时vector中删去这项任务,然后从这个idea对应的pm的优先队列中出队这个idea,然后如果pm的队列不空表示他还有没实现的idea,将这个pm的下一个idea放入临时vector

链接：https://www.nowcoder.com/questionTerminal/f76b7bc64e554edaa53d8e0d84f921c5?f=discussion
来源：牛客网

#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<iostream>
#include<list> 
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;
class idea {
public:
    int index;
    int pm_num;
    int proposed_time;
    int priority;
    int time_needed;

    idea(int index, int pm_num, int proposed_time, int priority, int time_needed)
    {
        this->index = index;
        this->pm_num = pm_num;
        this->proposed_time = proposed_time;
        this->priority = priority;
        this->time_needed = time_needed;
    }
    bool operator<(const idea& idea2) const {
        if (this->priority < idea2.priority)return true;
        else if (this->priority > idea2.priority)return false;

        if (this->time_needed > idea2.time_needed)return true;
        else if (this->time_needed < idea2.time_needed)return false;

        return(this->proposed_time > idea2.proposed_time);
    }
};

bool cmp_time(idea a, idea b)
{
    return a.proposed_time < b.proposed_time;
}

bool cmp_programmer(idea idea1, idea idea2)
{

    if (idea1.time_needed < idea2.time_needed)return true;
    else if (idea1.time_needed > idea2.time_needed)return false;


    return(idea1.pm_num < idea2.pm_num);
}

vector<int> proceed(int n, int m, int p, vector<idea>&ideas)
{
    int num_of_ideas_left = p;
    sort(ideas.begin(), ideas.end(), cmp_time);
    vector<int> ans;
    vector<priority_queue<idea> >ideas_has_been_proposed_group_by_pm(n+1);

    vector<vector<idea> >ideas_to_be_proposed_group_by_pm(n+1);


    int time_to_finish_current_idea[3010];
    int time_of_idea_completed[3010];
    for (int i = 0; i < 3010; i++) {
        time_to_finish_current_idea[i] = 0;
        time_of_idea_completed[i] = 0;
    }
    int current_time = 0;



    while (num_of_ideas_left) {
        current_time++;
        int index = 0;
        while (index < ideas.size() && ideas[index].proposed_time <= current_time)index++;

        for (int i = 0; i < index; i++)
            ideas_has_been_proposed_group_by_pm[ideas[i].pm_num].push(ideas[i]);
        ideas.erase(ideas.begin(), ideas.begin() + index);



        vector<idea>temp;
        for (int i = 1; i <= n; i++)
            if (!ideas_has_been_proposed_group_by_pm[i].empty())
                temp.push_back(ideas_has_been_proposed_group_by_pm[i].top());
        sort(temp.begin(), temp.end(), cmp_programmer);


        int i = 1;
        while (  i <= m) {
            if (time_to_finish_current_idea[i] > 0)
                time_to_finish_current_idea[i]--;
            if(time_to_finish_current_idea[i]==0&& !temp.empty())
             {
                idea idea0 = temp[0];
                time_to_finish_current_idea[i] = idea0.time_needed;
                temp.erase(temp.begin(), temp.begin() + 1);
                ideas_has_been_proposed_group_by_pm[idea0.pm_num].pop();
                if (!ideas_has_been_proposed_group_by_pm[idea0.pm_num].empty()) {
                    temp.push_back(ideas_has_been_proposed_group_by_pm[idea0.pm_num].top());
                    sort(temp.begin(), temp.end(), cmp_programmer);
                }
                time_of_idea_completed[idea0.index] = current_time + idea0.time_needed;
                num_of_ideas_left--;
            }
            i++;
        }
    }
    for (int i = 1; i <= p; i++)
        ans.push_back(time_of_idea_completed[i]);
    return ans;
}

int main() {
    /*
    int n = 2, m = 2, p = 5;
    idea idea1(1, 1, 1, 1, 2);
    idea idea2(2, 1, 2, 1, 1);
    idea idea3(3, 1, 3, 2, 2);
    idea idea4(4, 2, 1, 1, 2);
    idea idea5(5, 2, 3, 5, 5);
    vector<idea>ideas;
    ideas.push_back(idea1);
    ideas.push_back(idea2);
    ideas.push_back(idea3);
    ideas.push_back(idea4);
    ideas.push_back(idea5);
    vector<int>ans = proceed(n, m, p, ideas);

    for (int temp : ans)printf("%d\n", temp);
    getchar();
    */
    int n, m, p;
    int pm_num;
    int proposed_time;
    int priority;
    int time_needed;
    cin >> n >> m >> p;
    vector<idea>ideas;
    for (int i = 0; i < p; i++) {
        cin >> pm_num >> proposed_time >> priority >> time_needed;
        idea idea_temp(i + 1, pm_num, proposed_time, priority, time_needed);
        ideas.push_back(idea_temp);
    }
    vector<int>ans = proceed(n, m, p, ideas);

    for (int temp : ans)printf("%d\n", temp);
     return 0;
}