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

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

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

https://ac.nowcoder.com/acm/contest/950/D 

                                                  加工生产调度

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

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

输入格式:
第一行仅—个数据n(0<n<1000),表示产品的数量。

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

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

输出格式:
第一行一个数据,表示最少的加工时间。

第二行是n个整数,均为产品的原始标号,表示一种用时最短的产品加工顺序。

输入样例:
5
3 5 8 7 10
6 2 1 4 9
输出样例:
34
1 5 4 2 3
 

解析:

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

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

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

#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;
}