题解 P1248 【加工生产调度】

题目

某工厂收到了 n 个产品的订单，这 n 个产品分别在 A、B 两个车间加工，并且必须先在 A 车间加工后才可以到 B 车间加工。

某个产品 i 在 A、B 两车间加工的时间分别为 A_i,B_i

怎样安排这 n 个产品的加工顺序，才能使总的加工时间最短。

这里所说的加工时间是指：从开始加工第一个产品到最后所有的产品都已在 A、B 两车间加工完毕的时间

贪心

mind

排序

考虑两个产品，在A中加工时间a₁,a₂，在B中加工的时间为b₁,b₂

假设先加工产品1的方案较优

先加工1, time: a₁+max(b₁,a₂)+b₂

先加工2, time: a₂+max(b₂,a₁)+b₁

得到： a₁+max(b₁,a₂)+b₂ < a₂+max(b₂,a₁)+b₁

移项，得到 max(b₁,a₂)-a₂-b₁ < max(b₂,a₁)-b₂-a₁

手摸一下阔以知道： -min(b₁,a₂) < -min(b₂,a₁)

也就是 min(a₁,b₂)<min(₂,b₁)

按照这个排序

dalao们都说该式子不具传递性

详见……

怎么求值？？

还是考虑两个产品

根据图像显而易见了（from：_ztyqwq）

①

这种情况下 A_j <= B_i，time = A_i + B_i + B_j

②

这种情况下 A_j > B_i, time = A_i + A_j + B_j

综上：总时间为：A_i + max(A_j,B_i) + B_j

代码

/*

work by:Ariel

*/

#include <iostream>

#include <cstdio>

#include <queue>

#include <algorithm>

#include <cstring>

using namespace std;

const int M = 1e4 + 4;

typedef long long ll;

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 f*x;

}

struct node{

	int a,b,num;

}work[M];

int ans;

bool cmp(node x,node y){

    return min(x.a , y.b) < min(y.a , x.b);

}

int tima,timb;

int main()

{

  int n = read();

  for(int i = 1;i <= n; i++){

  	 work[i].a = read();

  	 work[i].num = i;

  }

  for(int i = 1;i <= n; i++){

  	 work[i].b = read();

  }

  sort(work + 1, work + n + 1, cmp);

  for(int i = 1;i <= n; i++){

  	 tima += work[i].a;

  	 timb = max(tima, timb) + work[i].b;

  }

    cout << timb <<"\n";

    for (int i = 1; i < n; i++) {

        cout << work[i].num << " ";

    }

    cout << work[n].num;

  return 0;

}

巴特西

题解 P1248 【加工生产调度】

题目

mind

最新文章

热门文章