P2751题解

GW_tzym · 2025-09-11 11:27:33 · 题解

题目大意

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

思路

这是一个很好的题，第一个子问题能帮我们更好的切入这个问题。考虑第一个子问题，我们怎么才能让所有物品通过机械 A加工的时常最短？\\ 很显然这是一个贪心，想一下，最优的办法就是从加工时间最短的开始往里面放物品，不断放，只要一有空闲的机械就往里放。这样就能保证所用时间最短。具体看代码：

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]。

那对于子问题二呢？显然上述贪心对于机械 B 的加工时常计算同样适用。但是一个问题，机械 A 和机械 B 要如何衔接呢？\\ 我们设 g[i] 为第 i 件完成 B 加工物品，那么答案是某一对 f[i],g[j] 之和的最大值，我们要使其最小。注意到 f,g 都是单调不减的，我们就让 f[i] 和 g[n-i+1] 配对，就能最小化答案 \\

完整代码

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