2020-08-18 作业调度方案

https://www.luogu.com.cn/problem/P1065

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <sstream>
#include <algorithm>
#include <cstring>
using namespace std;

long long qmi(int m, int k)
{
    int res = 1, t = m;
    while (k)
    {
        if (k&1) res = res * t;
        t = t * t;
        k >>= 1;
    }
    return res;
}

int read(){
    int x = 0,f = 1;
    char c = getchar();
    while (c<'0'||c>'9') {
        if (c=='-') {
            f = -1;
        }
        c = getchar();
    }
    while (c>='0'&&c<='9') {
        x = x*10+c-'0';
        c = getchar();
    }
    return x*f;
}

#define maxn 50
int n,m;
int ans = 0;

int worklist[maxn * maxn];//工作安排

int worknumber[maxn][maxn];//工作机器序号

int worktime[maxn][maxn];//加工时间

int cnt_now_work_step[maxn];//当前取到工件的工序牌号

int lasttime[maxn];//某个工件出现的最晚的时间（点）

bool timeline[maxn * maxn][maxn * maxn];//某一台机器在某一个时间（点）上是不是正在干活。

bool check_in_line(int begin_time_point, int end_time_length, int workid){//检查是否可以在生产线上
    for (int time = begin_time_point; time <= end_time_length;time++)
        if (timeline[workid][time])//若在产品线上
            return false;
    return true;
}

int main(){
    cin >> m >> n;//m台机器加工n个工件
    
    for (int i=1;i<=n*m;i++){
        cin >> worklist[i];//工作安排
    }

    /*
     其中前n行依次表示每个工件的每个工序所使用的机器号，
     第1个数为第1个工序的机器号，
     第2个数为第2个工序机器号，
     等等。
     */
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            cin >> worknumber[i][j];
        }
    }

    /*
     后n行依次表示每个工件的每个工序的加工时间。
    */
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            cin >> worktime[i][j];
        }
    }

    
    for (int i=1;i<=n*m;i++){//从1开始，一共有n*m个工作件
        int nowitem = worklist[i];//当前工作的工作件
        cnt_now_work_step[nowitem]++;//工序排号
        int nownumber = worknumber[nowitem][cnt_now_work_step[nowitem]];//工作的机器序号
        int costtime = worktime[nowitem][cnt_now_work_step[nowitem]];//花费的时间
        
        for (int time = lasttime[nowitem]+1; ;time++)//扫描时间轴
            if (check_in_line(time,time+costtime-1,nownumber)){//是否可以在线上
                for (int marktime = time; marktime <= time+costtime-1 ;marktime++)//占据时间线
                    timeline[nownumber][marktime] = true;
                lasttime[nowitem] = time + costtime - 1;//结尾时间
                break;//打断时间扫描
            }
    }

    for (int i=1;i<=n;i++)//机器数
        ans = max(ans,lasttime[i]);//取最大的尾数

    cout << ans << endl;

    return 0;
}
/*
2 3
1 1 2 3 3 2
1 2
1 2
2 1
3 2
2 5
2 4
============
10
*/