首页 > 代码库 > CODEVS——T3008 加工生产调度

CODEVS——T3008 加工生产调度

2024-10-15 05:21:02   209人阅读

http://codevs.cn/problem/3008/ 

 时间限制: 1 s
 空间限制: 128000 KB
 题目等级 : 黄金 Gold
 
 

题目描述 Description

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

    某个产品i在A、B两车间加工的时间分别为Ai、Bi。怎样安排这n个产品的加工顺序，才能使总的加工时间最短。这里所说的加工时间是指：从开始加工第一个产品到最后所有的产品都已在A、B两车间加工完毕的时间。

输入描述 Input Description

       第一行仅—个数据n(0<n<1000)，表示产品的数量。

       接下来n个数据是表示这n个产品在A车间加工各自所要的时间(都是整数)。

       最后的n个数据是表示这n个产品在B车间加工各自所要的时间(都是整数)。

输出描述 Output Description

      第一行一个数据，表示最少的加工时间；

样例输入 Sample Input

5

3 5 8 7 10

6 2 1 4 9

样例输出 Sample Output

34

数据范围及提示 Data Size & Hint

0<n<1000

分类标签 Tags 点此展开 

贪心
 
Johnson算法——流水作业
 1 #include <algorithm> 2 #include <cstdio> 3  4 using namespace std; 5  6 const int N(1000+15); 7 int n,a[N],b[N]; 8  9 struct Node10 {11     int num,tim,a_b;//工作编号，用时，机器号 12     bool operator < (const Node &x) const13     { return tim<x.tim; }//最短时间 14     Node(int num=0,int tim=0,int a_b=0):15         num(num),tim(tim),a_b(a_b){}16 }job[N];17 int ans,num[N],sum[N];18 void Johnson()19 {20     for(int i=1;i<=n;i++)21         if(a[i]<b[i]) job[i]=Node(i,a[i],0);22         else job[i]=Node(i,b[i],1);23     sort(job+1,job+n+1);24     for(int l=0,r=n+1,i=1;i<=n;i++)//得到最优解 25         if(job[i].a_b==0) num[++l]=job[i].num;26         else num[--r]=job[i].num;27 }28 29 int main()30 {31     scanf("%d",&n);32     for(int i=1;i<=n;i++) scanf("%d",a+i);33     for(int i=1;i<=n;i++) scanf("%d",b+i);34     Johnson();35     for(int i=1;i<=n;i++) sum[i]+=sum[i-1]+a[num[i]];36     ans=sum[1]+b[num[1]];37     for(int i=2;i<=n;i++) ans=max(sum[i],ans)+b[num[i]];38     printf("%d\n",ans);39     return 0;40 }

 

CODEVS——T3008 加工生产调度


联系
我们