USACO4.2 工序安排Job Processing

wjh15101051's space

卧薪尝胆，厚积薄发。

Date: Fri Aug 03 10:34:57 CST 2018

In Category: NoCategory

Description：

有 $n$ 个产品， $m_1$ 个 $A$ 机器 $m_2$ 个 $B$ 机器，给出每台机器完成一次操作的时间，计算完成 $A$ 的时间的最小值和完成 $B$ 的时间的最小值。

$1\leqslant n\leqslant1000$

Solution：

首先先考虑第一问，那么要让最大的结束时间最小，那么就每次在堆中找一个结束时间最小的把他扩展后再丢回堆里，也就是说堆中存储的时当前状态再做一个的值。

然后再考虑第二问，发现第一问中有这么一个性质，也就是结束时间一定是递增的，那么对于第二个就不难想到肯定是在原来的顺序倒着处理，那么这样再求一遍再倒叙加起来取最大就行了。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n,m1,m2;

#define MAXM 31

struct machine

{

	int cur,tim;

	bool operator < (const machine &b)const

	{

		return cur > b.cur;

	}

}a[MAXM],b[MAXM];

#define MAXN 1010

int s[MAXN];

bool cmp(int a,int b){return a > b;}

int main()

{

	scanf("%d%d%d",&n,&m1,&m2);

	priority_queue<machine> q;

	for(int i = 1;i <= m1;++i)

	{

		scanf("%d",&a[i].tim);

		a[i].cur = a[i].tim;

		q.push(a[i]);

	}

	int ans1 = 0,ans2 = 0;

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

	{

		machine k = q.top();q.pop();

		s[i] = k.cur;

		ans1 = max(ans1,k.cur);

		k.cur += k.tim;

		q.push(k);

	}

	for(int i = 1;i <= m1;++i)q.pop();

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

	for(int i = 1;i <= m2;++i)

	{

		scanf("%d",&b[i].tim);

		b[i].cur = b[i].tim;

		q.push(b[i]);

	}

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

	{

		machine k = q.top();q.pop();

		ans2 = max(ans2,k.cur + s[i]);

		k.cur += k.tim;

		q.push(k);

	}

	cout << ans1 << " " << ans2 << endl;

	return 0;

}

In tag: 算法-贪心

wjh15101051