欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

加工生产调度————(贪心)

程序员文章站 2022-03-25 17:27:13
...

链接:https://ac.nowcoder.com/acm/problem/5016

 

 

题目描述

某工厂收到了n个产品的订单,这n个产品分别在 A、B 两个车间加工,并且必须先在 A 车间加工后才可以到 B 车间加工。
某个产品i在 A,B 两车间加工的时间分别为 AiA_iAi​,BiB_iBi​。怎样安排这n个产品的加工顺序,才能使总的加工时间最短。
这里所说的加工时间是指:从开始加工第一个产品到最后所有的产品都已在 A,B 两车间加工完毕的时间。

输入描述:

第一行仅—个数据n,表示产品的数量;
接下来n个数据是表示这n个产品在A车间加工各自所要的时间;
最后的n个数据是表示这n个产品在B车间加工各自所要的时间。

输出描述:

第一行一个数据,表示最少的加工时间;
第二行是一种最小加工时间的加工顺序。

示例1

输入

复制

5
3 5 8 7 10
6 2 1 4 9

输出

复制

34
1 5 4 2 3

备注:

对于100%100\%100%的数据,0<n<1000 ,所有数值皆为整数。
本题的 SPJ 对行尾多余空格敏感,各位输出答案时不要留行尾多余空格~

解析:(来自振国哥)

       这是一道很经典的题,只需要记住这种题型的一个结论:

       A机器上加工时间短的任务应优先,而在B机器上加工时间短的任务应该排在后面。

 加工生产调度————(贪心)

 

AC代码:

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#include<cmath>
#include<string>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
 
struct node {
    int id,x,y;
}a[1001];
struct Node {
    int id, num;
}b[1001];
int cmp(Node x, Node y) {
    return x.num < y.num;
}
int ans[1001];
 
int main() {
    ll n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].x;
        a[i].id = i;
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i].y;
        b[i].num = min(a[i].x, a[i].y);//记录每个产品的最小工序时间
        b[i].id = i;
    }
    sort(b + 1, b + 1 + n, cmp);//按照最小工序时间从小到大排序
    int l=1, r=n;
    for (int i = 1; i <= n; i++) {
        //如果最小工序时间是第一道工序,就将其安排到前面
        if (b[i].num == a[b[i].id].x)ans[l++] = b[i].id;
        //如果最小工序时间是第二道工序,就将其安排到后面
        else ans[r--] = b[i].id;
    }
    //这样,ans就保存下来加工产品的最优顺序编号
    ll sum1=0, sum2=0;
    //sum1记录加工完第i个产品的第一道工序后所用的时间
    //sum2记录加工完第i个产品的第二道工序后所用的最优时间
    for (ll i = 1; i <= n; i++) {
        sum1 += a[ans[i]].x;
        //还没有加工第i个的第二道程序之前总时间取决于sum1,和sum2的最大值。
        sum2 = max(sum1, sum2);
        //之后在执行第二道工序
        sum2 += a[ans[i]].y;
    }
    cout << sum2 << endl;
    for (ll i = 1; i < n; i++) {
        cout << ans[i] << " ";
    }
    cout << ans[n] << endl;
    return 0;
}

 

AC代码(自己写的)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<vector>
#include<string>
using namespace std;
typedef long long ll;
int n;
struct node{
	int id;
	int x,y;
}f[1005];
struct note{
	int id;
	int sum;
}g[1005];
bool cmp(note u,note v)
{
	return u.sum <v.sum ;
}
int a[1005];
int main()
{
	cin>>n;
	int i,j,k;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&f[i].x );
		f[i].id =i;
	}
	for(i=1;i<=n;i++)
	{
		scanf("%d",&k );
		g[i].id =i;
		g[i].sum =min(f[i].x ,k);
		f[i].y =k;
	}
	sort(g+1,g+n+1,cmp);
	for(i=1,j=1,k=n;i<=n;i++)//排列位置 
	{
		if(g[i].sum ==f[g[i].id ].x )
		{
			a[j++]=g[i].id ;
		}
		else{
			a[k--]=g[i].id ;
		}
	}
	int ans=0,cnt=0;
	for(i=1;i<n;i++)
	{
		if(f[a[i]].y<=(f[a[i+1]].x-cnt))
		{
			ans+=f[a[i+1]].x-cnt;//注意 
			cnt=0;
		}
		else {
			cnt=f[a[i]].y-f[a[i+1]].x+cnt;
			ans+=f[a[i]].y ;
		}
	}
	ans+=f[a[1]].x ;
	ans+=f[a[n]].y ;
	cout<<ans<<endl;
	for(i=1;i<n;i++)
	{
		printf("%d ",a[i]);
	}
	printf("%d\n",a[n]);
	return 0;
}