【编程题目 |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%内容,订阅会员后查看


隐藏内容

此处内容需要权限查看

  • 普通用户特权:11金币
  • 会员用户特权:免费
  • 永久会员用户特权:免费推荐
会员免费查看

C++解法二


#include <bits/stdc++.h>

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


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


隐藏内容

此处内容需要权限查看

  • 普通用户特权:11金币
  • 会员用户特权:免费
  • 永久会员用户特权:免费推荐
会员免费查看