AcWing 488. 作业调度方案
原题链接
中等
作者:
acwing_685
,
2019-10-30 20:43:31
,
所有人可见
,
阅读 1226
C++ 代码
//个人感觉自己的思路比较易懂,所以在代码里加点注释方便其他oier食用
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0,f=1;
char c=getchar();
while((c<'0'||c>'9')&&c!='-')c=getchar();
if(c=='-')f=-1,c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f*x;
}
int n,m,a[401],id[21][21],ti[21][21],cnt[21],last[21],ans;
//id[i][j]记录第i个工件第j道工序要在哪个机器上进行
//ti[i][j]记录每个工序所需要的时间
//cnt[i]记录第i个工件进行到第几个工序了
//last[i]记录第i个工件上一道工序的结束时间
priority_queue<pair<int,int> > q[21];
//q[i]记录第i号机器积累下来的所有能用的空档(要用优先队列的原因是把每个空档的左端点排序,这样的话遍历优先队列的时候找到的第一个符合条件的空档一定是所有符合条件的空档中最前面的)
vector<pair<int,int> > k;
//k是遍历优先队列的时候辅助用的,具体看下面
int main(){
m=read();
n=read();
for(register int i=1;i<=n*m;++i)a[i]=read();
for(register int i=1;i<=n;++i)
for(register int j=1;j<=m;++j)id[i][j]=read();
for(register int i=1;i<=n;++i)
for(register int j=1;j<=m;++j)ti[i][j]=read();
//上头的都是读入
for(register int i=1;i<=m;++i)q[i].push(make_pair(0,1e5));
//先给每台机器一个足够大的空档,因为还没开始加工
for(register int i=1;i<=n*m;++i)
{
++cnt[a[i]];
int t=id[a[i]][cnt[a[i]]];
int s=ti[a[i]][cnt[a[i]]];
//t是当前工序要用的机器
//s是当前工序要用的时间
k.clear();
//k用来保存在找到合法空档之前,出现的其他空档(因为优先队列没法用下标遍历,只能把前面遍历出来的先存着,之后再给它放回去)
while(!q[t].empty())
{
int x=-q[t].top().first;
int y=q[t].top().second;
//注意:因为优先队列默认pair的排序方法是按first从大到小排,而我们需要所有空档的左端点从小到大排,所以我们把左端点反着存,取的时候自然也反着取
q[t].pop();
k.push_back(make_pair(-x,y));
//把合法空档之前出现的空档先存进k
if(x<last[a[i]])
{
if(y-last[a[i]]<s)continue;//当前空档没法进行此项工序
k.pop_back();
k.push_back(make_pair(-x,last[a[i]]));
k.push_back(make_pair(-last[a[i]]-s,y));
//当前空档可以进行此项工序,就先把它弄k里弄出来,拆成完成工序后的剩余空档在放进去
last[a[i]]+=s;
ans=max(ans,last[a[i]]);
//更新
}
else
{
if(y-x<s)continue;//当前空档没法进行此项工序
k.pop_back();
k.push_back(make_pair(-x-s,y));
//当前空档可以进行此项工序,就先把它弄k里弄出来,拆成完成工序后的剩余空档在放进去
last[a[i]]=x+s;
ans=max(ans,last[a[i]]);
//更新
}
break;
}
int len=k.size();
for(register int i=0;i<len;++i)q[t].push(k[i]);//把之前遍历出来的又给弄回去
}
printf("%d\n",ans);
return 0;
}