首页 > 其他分享 >[NOIP2006 提高组] 作业调度方案 题解

[NOIP2006 提高组] 作业调度方案 题解

时间:2024-10-09 19:49:01浏览次数:10  
标签:NOIP2006 顺序 每个 int 题解 安排 调度 工件 工序

题目描述

我们现在要利用 m 台机器加工 n 个工件,每个工件都有 m 道工序,每道工序都在不同的指定的机器上完成。每个工件的每道工序都有指定的加工时间。

每个工件的每个工序称为一个操作,我们用记号 j-k 表示一个操作,其中 j 为 1 到 n 中的某个数字,为工件号;k 为 1 到 m 中的某个数字,为工序号,例如 2-4 表示第 2 个工件第 4 道工序的这个操作。在本题中,我们还给定对于各操作的一个安排顺序。

例如,当 n=3,m=2 时,1-1,1-2,2-1,3-1,3-2,2-2 就是一个给定的安排顺序,即先安排第 1 个工件的第 1 个工序,再安排第 11 个工件的第 22 个工序,然后再安排第 2 个工件的第 1 个工序,等等。

一方面,每个操作的安排都要满足以下的两个约束条件。

  1. 对同一个工件,每道工序必须在它前面的工序完成后才能开始;

  2. 同一时刻每一台机器至多只能加工一个工件。

另一方面,在安排后面的操作时,不能改动前面已安排的操作的工作状态。

由于同一工件都是按工序的顺序安排的,因此,只按原顺序给出工件号,仍可得到同样的安排顺序,于是,在输入数据中,我们将这个安排顺序简写为 1 1 2 3 3 2

还要注意,“安排顺序”只要求按照给定的顺序安排每个操作。不一定是各机器上的实际操作顺序。在具体实施时,有可能排在后面的某个操作比前面的某个操作先完成。

输入格式

第 1 行为两个正整数 m, n,用一个空格隔开, 其中 m(<20) 表示机器数,n(<20) 表示工件数。

第 2 行:m×n 个用空格隔开的数,为给定的安排顺序。

接下来的 2n 行,每行都是用空格隔开的 m 个正整数,每个数不超过 20。

其中前 n 行依次表示每个工件的每个工序所使用的机器号,第 1 个数为第 1 个工序的机器号,第 2 个数为第 2 个工序机器号,等等。

后 n 行依次表示每个工件的每个工序的加工时间。

可以保证,以上各数据都是正确的,不必检验。

输出格式

11 个正整数,为最少的加工时间。

输入输出样例

输入 #1

2 3
1 1 2 3 3 2
1 2 
1 2 
2 1
3 2 
2 5 
2 4

输出 #1

10

题目解析

这是一道模拟题,主要需要考虑以下几个约束条件:

  1. 每个工件的下一个工序必须在上一个工序之后
  2. 同一台机器同一时刻只能加工一个工件
  3. 按题目顺序安排下一个工件

按照题目说的做,不会错。

我的题解一般会放一组福利数据,这次也不例外。洛谷官方数据测试点#2奉上,附解释。

数据

input

3 3
1 1 1 2 3 3 2 2 3
1 2 3
2 1 3
2 3 1
7 2 4
3 2 5
3 2 3

output

18

附:我的代码

#include <stdio.h>

int m, n;
int list[501];
struct Information {
    int id;
    // 在第 id 台机器上加工
    int cost;
    // 花费 cost 时间
} a[21][21];
// a[第几个工件][第几步]
int mac[21][100001] = {0};
// mac[机器编号][时间(话说我也不知道时间最大是多少,反正在空间限制内尽量大)]
int step[21] = {0};
// 每个工件加工到了第几步
int las_time[21] = {0};
// 每个工件上次是 las_time[工件编号] 时加工完的
int ans = 0;

int main()
{
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= m * n; i++) {
        scanf("%d", list + i);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j].id);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j].cost);
        }
    }
    // 以上:读入
    for (int i = 1; i <= m * n; i++) {
        int now = list[i];
        step[now]++;
        int id = a[now][step[now]].id, cost = a[now][step[now]].cost;
        /* 调试代码 */ // printf("%d: now = %d, id = %d, cost = %d\n", i, now, id, cost);
        int s = 0;
        for (int j = las_time[now] + 1; ; j++) {
            if (mac[id][j] == 0) {
                s++;
            } else {
                s = 0;
            }
            if (s == cost) {
                for (int k = j - cost + 1; k <= j; k++) {
                    mac[id][k] = 1;
                }
                /* 调试代码 */ // printf("(%d~%d. \n", j - cost + 1, j);
                if (j > ans) ans = j;
                las_time[now] = j;
                break;
            }
        }
    }
    printf("%d", ans);
    return 0;
}

 在百忙之中写一篇题解也比较辛苦,麻烦拿拿你们皇帝般的纤纤玉手帮我点点赞。

标签:NOIP2006,顺序,每个,int,题解,安排,调度,工件,工序
From: https://blog.csdn.net/geogenotfound/article/details/142724889

相关文章

  • NewStar CTF 2024 week1 题解
    1.base题目给了以下内容:Thisisabasequestion!4C4A575851324332474E324547554B494A5A4446513653434E564D444154545A4B354D45454D434E4959345536544B474D5134513D3D3D3D观察给出的字符串发现,字符串由数字0-9以及字母A-F组成,于是推测这可能是一个base16编码,于是将其解码,......
  • 2023牛客OI赛前集训营-提高组(第三场) - 题解汇总
    空位与数(game)贪心即可,因为正正得正,负负也得正,所以将两个数组分别按照正负性分开,然后让正数里面大的配上大的,负数里面绝对值大的配上绝对值大的,这样可以让正积总和尽量大。剩下不足的(必须要一正一负相乘的)让绝对值大的配绝对值小的,这样可以让负积总和尽量小。#include<cstdio>#i......
  • webapi发布---问题解决
    一.127.0.0.1是回路地址,来检验本机TCP/IP协议栈,实际使用过程中服务端不在本机,是外部地址,要用IP地址测试。外部用户采用IP+端口号访问,如下图浏览器访问不了,400错误。解决方案:因为IIS7采用了更安全的web.config管理机制,默认情况下会锁住配置项不允许更改。以管理员身份运......
  • 题解:SP6517 JOCHEF - Farmer Sepp
    一眼简单悬线法,而且有多倍经验,感觉这题被遗忘了,那我就拿下这个水紫吧!我们用a数组表示能向上延伸能到达的最大距离,依次遍历每一行,如果该位置为F,他可以从上一行转移过来,将a数组增加一,如果该位置为C,意味着这个位置不能成矩形,将a数组变为0。接下来进行悬线法的标准操作,设l......
  • 使用宝塔快速搭建配置Openai api接口代理+502 Bad Gateway网关错误问题解决
    本教程提供了一种简便快捷的方法,无需复杂步骤,极易操作,实现零代码、零部署的快速接入。实现准备1.服务器,这里使用阿里香港轻量服务器)2.OpenAI官方的模型apikey3.使用第三方系统或插件进行测试关于第三方网站系统或插件:《SparkAI系统介绍文档-渐进式AIGC系统》开......
  • P10673 【MX-S1-T2】催化剂 题解
    要解决这个问题,我们需要高效地处理动态更新的糖果种类数量,并在每次询问时快速计算最小的愤怒值总和。以下是详细的解决方案和实现步骤:问题分析糖果的种类和数量:每个糖果有一个类型,代表不同的种类。我们需要跟踪每种类型的糖果数量,以便在分配时计算重复的糖果数量,从而确定愤......
  • 总奖金高达10万元!华为算法精英实战营“亲和任务调度系统”来啦!
    随着物联网、大数据、AI时代的到来,时延、可靠性等指标要求越来越高,海量的数据分析、大量复杂的运算对CPU的算力要求越来越高。CPU内部的大部分资源用于缓存和逻辑控制,适合运行具有分支跳转、逻辑复杂、数据结构不规则、递归等特点的串行程序。在集成电路工艺制程将要达到极限,摩尔......
  • AT_abc374_c [ABC374C] Separated Lunch 题解
    题目传送门右侧可以传送到原题位置。题目大意题目描述由于KEYENCE总部的员工越来越多,他们决定将总部各部门分成两组,错开午休时间。KEYENCE总部有NNN个部门,第......
  • 在K8S中,Pod常见调度方式有哪些?
    在Kubernetes(K8s)中,Pod的调度是一个关键过程,它决定了Pod在集群中的哪个节点上运行。K8s提供了多种调度方式,以满足不同应用的需求。以下是Pod常见的调度方式:1.默认调度(自由调度)功能:Kubernetes的默认调度器(kube-scheduler)会根据一系列内置的调度策略自动选择适合的节点。考虑因......
  • 弹珠 题解
    题意求\(n\)个一样的球放到\(k\)个盘子里的方案数(每个盘子至少一个)。题解考虑记\(f(i,j)\)为结果。我们可以一次性只加一个球(新放到一个盘子里),也就是可以从\(f(i-1,j-1)\)转移过来。也可以用已有的盘子每个盘子放一个球,就是从\(f(i-j,j)\)转移过来。为......