洛谷题目链接:[USACO4.2]工序安排Job Processing

题目描述

一家工厂的流水线正在生产一种产品，这需要两种操作：操作A和操作B。每个操作只有一些机器能够完成。

Ioi96d1.gif

上图显示了按照下述方式工作的流水线的组织形式。A型机器从输入库接受工件，对其施加操作A，得到的中间产品存放在缓冲库。B型机器从缓冲库接受中间产品，对其施加操作B，得到的最终产品存放在输出库。所有的机器平行并且独立地工作，每个库的容量没有限制。每台机器的工作效率可能不同，一台机器完成一次操作需要一定的时间。

给出每台机器完成一次操作的时间，计算完成A操作的时间总和的最小值，和完成B操作的时间总和的最小值。

注：1、机器在一次操作中干掉一个工件； 2、时间总和的意思是最晚时间点

输入输出格式

输入格式：

第一行 三个用空格分开的整数：N，工件数量 (1<=N<=1000);M1，A型机器的数量 (1<=M1<=30);M2，B型机器的数量 (1<=M2<=30)。

第二行…等 M1个整数（表示A型机器完成一次操作的时间，1..20），接着是M2个整数（B型机器完成一次操作的时间，1..20）

输出格式：

只有一行。输出两个整数：完成所有A操作的时间总和的最小值，和完成所有B操作的时间总和的最小值（A操作必须在B操作之前完成）。

输入输出样例

输入样例#1：

5 2 3
1 1 3 1 4

输出样例#1：

3 5

说明

题目翻译来自NOCOW。

USACO Training Section 4.2

题意: 给每个工件进行\(A,B\)两种加工,一个工件的两种加工不能同时进行,一个机器也不能同时对两个工件进行处理.

题解: 一道隐藏在网络流专题中的贪心.

只考虑进行\(A\)加工,那么显然可以贪心选生产队列中完成时间最小的,这个可以用堆来模拟选择机器的过程.

那么如何处理\(B\)加工呢?其实在处理完\(A\)加工之后,每个工件的\(A\)加工结束时间就可以确定了,那么再根据贪心的思想,最后被加工完\(A\)步骤的工件的一定要选一个加工\(B\)步骤时间最小的机器,再用堆模拟一下就可以了.

话说我连这都没想到...果然还是思维跳不出来,果然还是建不出网络流的模

#include<bits/stdc++.h>
using namespace std;
const int N = 1000+5;
const int inf = 0x3f3f3f3f;

int n, m1, m2, t[N], ansa = 0, ansb = 0, f[N];

struct machine{
    int id, tim;
    bool operator < (const machine &a) const {
        return tim > a.tim;
    }
};

bool cmp(int x, int y){ return x > y; }

int main(){
    freopen("job.in", "r", stdin);
    freopen("job.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin >> n >> m1 >> m2;
    for(int i = 1; i <= m1; i++) cin >> t[i];
    for(int i = m1+1; i <= m1+m2; i++) cin >> t[i];
    priority_queue <machine> q;
    for(int i = 1; i <= m1; i++) q.push((machine){ i, t[i] });
    for(int i = 1; i <= n; i++){
        machine x = q.top(); q.pop();
        f[i] = x.tim, q.push((machine){ x.id, x.tim+t[x.id] });
        ansa = max(ansa, f[i]);
    }
    while(!q.empty()) q.pop();
    sort(f+1, f+n+1, cmp);
    for(int i = m1+1; i <= m1+m2; i++) q.push((machine){ i, t[i] });
    for(int i = 1; i <= n; i++){
        machine x = q.top(); q.pop();
        ansb = max(ansb, f[i]+x.tim);
        q.push((machine){ x.id, x.tim+t[x.id] });
    }
    cout << ansa << ' ' << ansb << endl;
    return 0;
}