仪器云使用的调度

【编程题目 |200分】仪器云使用的调度【2021考试题】

时间限制：C/C++ 1秒，其他语言 2秒

空间限制：C/C++262144K，其他语言524288K

64bit IO Format：%lld

本题可使用本地IDE编码，不能使用本地已有代码，无跳出限制，

编码后请点击”保存并调试“按钮进行代码提交。

■ 题目描述

仪器云使用的调度

• 生产车间有贵重仪器N台，并有需要使用仪器的生产测试设备数量K台，而且设定了每台生产测试设备要占用仪器的时间和优先级为[T, P]。
• 通过合理调度分配后，要求所有生产测试设备要占用贵重仪器的测试项目都执行完成，所需要的最少时间。
• 仪器数量N：1 <= N =< 1000；
• 生产设备数量K：1 <= K < 1000；

说明：

• 优先级越高的生产测试设备优先使用仪器，P的数字越小优先级越高；
• 当优先级相同的情况下，占用时间长的优先执行。

输入描述：

• 第一行输入为N和K，N表示生产车间的贵重仪器数量，K表示需要使用仪器的生产测试设备数量；
• 之后有K行，每一行表示一台生产测试设备要占用仪器的时间和优先级为[T, P]；
• 1 <= N =< 1000，1 <= K < 1000，1 <= T =< 1000，1 <= P < 1000

输出描述：

• 输出所有生产测试设备要占用贵重仪器的测试项目都执行完成，所需要的最少时间。

样例1：

输入

2 2

3 1

4 2

输出

4

解释：

题目解析：

可以分配使用的仪器有2台；占用时间越长，优先级越高的生产测试设备优先使用仪器；

[4,2]分配使用仪器1，[3,1]分配使用仪器2；

生产测试设备数量与仪器数量相等，所以需要花费的时间就是取占用仪器最长的时间，结果是4。

样例2：

输入

3 7

1 1

4 1

5 3

4 2

2 1

3 3

2 1

输出

8

解释：

题目解析：

可以分配使用的仪器有3台；占用时间越长，优先级越高的生产测试设备优先使用仪器；

（1） [4,1]分配使用仪器1，[2,1]分配使用仪器2，[2,1]分配使用仪器3；

（2） [1,1]分配使用仪器2，[4,2]分配使用仪器3，[5,3]分配使用仪器2；

（3） [3,3]分配使用仪器1；

所有生产测试设备都执行完后，需要花费的时间就是取占用仪器最长的时间，结果是8。

代码实现

C++解法一

#include <bits/stdc++.h>

using namespace std;

struct node {
    int t, p;
    bool operator<(const node &a) const {
        if (this->p == a.p) return this->t < a.t;
        return this->p > a.p;
    }
};

剩余50%内容，订阅会员后查看

C++解法二

#include <bits/stdc++.h>

using namespace std; 
const int maxn = 1e3+ 10, mod = 1e9 + 7, inf = 0x3f3f3f3f; 
int n, k, ans[maxn];

剩余50%内容，订阅会员后查看

STICK永久会员

打赏 收藏 海报 链接