跳到主要内容

该谁管了

题目描述​

某个部门有n名员工，编号从1到n。初始时，每名员工当前承担的总任务量都为0。

现在给定一个长度为m的任务数组tasks，其中tasks[i]表示第i天（0 ≤ i < m）需要处理的任务量。

公司规定，每天必须将当天的任务量全部分配给某一名员工。分配规则如下：

  1. 优先原则：选择当前累计承担任务总量最少的员工。
  2. 编号原则：如果有多名员工当前的累计任务总量相同且均为最少，则选择其中编号最小的员工。

请实现一个算法，模拟这一分配过程，并返回一个长度为m的数组answer，其中answer[i]表示第i天被分配任务的员工编号。

输入描述​

第一行包含两个整数 n和 m，分别表示员工人数和天数。

第二行包含m个整数，表示每天的任务量tasks[i]。

  • 1 ≤ n ≤ 10^5 （员工人数）
  • 1 ≤ m ≤ 10^5 （天数）
  • 1 ≤ tasks[i] ≤ 10^9 （每天的任务量）

输出描述​

输出一行，包含m个整数，表示每天分配到的员工编号，整数之间用空格隔开。

示例​

输入：
2 2
5 3

输出：
1 2

解释:
第0天：两名员工累计任务均为0，取编号最小的1号，分配5，此时(5, 0)。
第1天：2号累计为0最少，分配3，输出1 2。

解题思路​

堆排序

  1. 使用小根堆，每次弹出堆顶元素，该元素放入 answer[]
  2. 把当天的任务加给它
  3. 再加入到堆中进行下一轮分配

时间复杂度: O(mlogn) 空间复杂度: O(m+n)

C++ 解法​

#include <functional>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

vector<int> assignTasks(int n, vector<int> &tasks)
{
    int days_count = tasks.size();

    // 创建小根堆,堆元素为 pair{task,person},编号 i 的 person 承担的 task
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
    for (int i = 1; i ≤ n; i++) {
        minHeap.emplace(0, i);
    }

    vector<int> answer;
    answer.reserve(days_count);

    // 分配 task
    for(int day = 0; day < days_count; day++>) {
        // 取出当前任务量最少且编号最小的人
        auto [task, person] = minHeap.top();
        minHeap.pop();

        // 记录这一天分配给了谁
        answer.emplace_back(person);

        // 这个人增加当天的任务量
        task += tasks[day];
        minHeap.emplace(task, person);
    }

    return answer;
}

int main()
{
    int n, m;
    cin >> n >> m;

    // 填充 task
    vector<int> tasks(m, 0);
    for (int i = 0; i < m; i++) {
        cin >> tasks[i];
    }

    // 输出结果
    auto answer = assignTasks(n, tasks);
    for (int i = 0; i < m; i++) {
        if (i > 0) cout << " ";
        cout << answer[i];
    }
    cout << endl;

    return 0;
}