专栏文章

P2751题解

GGW_tzym
P2751题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minxwwqt
此快照首次捕获于
2025/12/02 10:09
3 个月前
此快照最后确认于
2025/12/02 10:09
3 个月前
查看原文

题目大意

有 nn件物品，m1m1 个机械 A，m2m2 个机械 B，每个机械进行加工都需要一定的时间，每件物品加工都必须经过机械 A 和机械 B，并且是先 A 后 B。问物品经过机械 A 加工的最小时常和所有物品加工完成的时常。\\

思路

这是一个很好的题，第一个子问题能帮我们更好的切入这个问题。考虑第一个子问题，我们怎么才能让所有物品通过机械 A加工的时常最短？\\ 很显然这是一个贪心，想一下，最优的办法就是从加工时间最短的开始往里面放物品，不断放，只要一有空闲的机械就往里放。这样就能保证所用时间最短。具体看代码：
CPP
priority_queue<PII,vector<PII>,greater<PII> >a1;
for(int i=1;i<=m1;i++)
	{
		cin>>a[i];//读入每个机械A所用的时常
		a1.push({a[i],i});//用优先队列找用时最少的（用时=等待时常+加工时常）
	}
for(int i=1;i<=n;i++)
{
	PII p1=a1.top();
	a1.pop();
	f[i]=p1.first;//设f[i]是第i件完成A加工物品
	a1.push({p1.first+a[p1.second],p1.second});//更新用时
}
显然，答案为 f[n]f[n]。
那对于子问题二呢？显然上述贪心对于机械 B 的加工时常计算同样适用。但是一个问题，机械 A 和机械 B 要如何衔接呢？\\ 我们设 g[i]g[i] 为第 ii 件完成 B 加工物品，那么答案是某一对 f[i],g[j]f[i],g[j] 之和的最大值，我们要使其最小。注意到 f,gf,g 都是单调不减的，我们就让 f[i]f[i] 和 g[n−i+1]g[n-i+1] 配对，就能最小化答案 \\

完整代码

CPP
#include<iostream>
#include<queue>
using namespace std;
#define PII pair<int,int>
int a[33],b[33];
priority_queue<PII,vector<PII>,greater<PII> >a1;
priority_queue<PII,vector<PII>,greater<PII> >b1;
int f[1001],g[1001];
int main()
{
	int n,m1,m2;
	cin>>n>>m1>>m2;
	for(int i=1;i<=m1;i++)
	{
		cin>>a[i];
		a1.push({a[i],i});
	}
	for(int i=1;i<=m2;i++)
	{
		cin>>b[i];
		b1.push({b[i],i});
	}
	for(int i=1;i<=n;i++)
	{
		PII p1=a1.top();
		a1.pop();
		f[i]=p1.first;
		a1.push({p1.first+a[p1.second],p1.second});
		
		PII p2=b1.top();
		b1.pop();
		g[i]=p2.first;
		b1.push({p2.first+b[p2.second],p2.second});
	}
	cout<<f[n]<<" ";
	int ans=0;
//	for(int i=1;i<=n;i++)
//	{
//		cout<<f[i]<<" ";
//	}
//	cout<<'\n';
//	for(int i=1;i<=n;i++)
//	{
//		cout<<g[i]<<" ";
//	}
//	cout<<'\n';
	for(int i=1;i<=n;i++)
	{
		ans=max(ans,f[i]+g[n-i+1]);
	}
	cout<<ans;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...