【作业调度方案】 （C++代码）

解题思路:





注意事项:





参考代码:

这道题...我认为是一道不能算“简单”的模拟

首先，出题者不仅在考察代码实现能力，

更在考验你的语文水平（ 唉...... ）

闲话不多说了，注释都在代码里了...

cpp..

#include<bits/stdc++.h>     // 烂大街的头文件using namespace std;int work[21];         //  记录第 i 个工件所做的工序int num[501];         //  记录第 i 个工序的安排序列int lasttime[21];       //  记录第 i 号工件当前所用的最晚时间int time[21][21];       //  记录 i 号工件第 j 个工序所用的时间int need[21][21];      //  记录 i 号工件第 j 个工序所需的机器bool mac[21][501];     //  记录 i 号机器第 j 分钟的状态（ 是否空闲 ）int main(){    int m,n,ans=0,s=0;    scanf("%d%d",&m,&n);    for(int i=1;i<=m*n;i++)        scanf("%d",&num[i]);    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++)            scanf("%d",&need[i][j]);    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++)            scanf("%d",&time[i][j]);    //  输入完毕，准备开始 “ ‘ 易懂 ’ ” 的核心部分
   for(int i=1;i<=n*m;i++)
   {
       work[num[i]]++;    //  工序++
       for(int j=lasttime[num[i]]+1;;j++)    //  寻找机器空闲状态的循环
       {            if(mac[need[num[i]][work[num[i]]]][j]==0)    // ... 查看机器是否空闲...（ 注意看清括号 ）
               s++;            else  s=0;            if(s==time[num[i]][work[num[i]]])    //  机器表示：我闲着！！
           {                for(int k=j-s+1;k<=j;k++)    //  在这段时间上安排工作
                   mac[need[num[i]][work[num[i]]]][k]=1;
               lasttime[num[i]]=j;    //  注意更新最晚时间
               s=0;    //  必要的
               break;    //  操作
           }
       }
   }    // 简短的核心部分
   for(int i=1;i<=n;i++)
       ans=max(ans,lasttime[i]);    //  总时间即为某工件的最晚时间
   printf("%d",ans);    return 0;    //  庄严的结束程序..}

祝大家 NOIP 2017 RP++

while(RP++)
{
}printf("%lld",RP);

评论

还没有评论

评论

作者: ShawnZhou 更新时间: 2017-09-11 01:42  在Ta的博客查看  1 

安利一发自己的博客：http://www.cnblogs.com/OIerShawnZhou/

（我平常写的题解都会往博客里发，欢迎各位大佬前来拍砖）

超难理解的一道题。嘴上说着是一道大模拟实际上无法理解题意就会让事情变得巨麻烦。

强烈建议画图研究样例。

这是目前为止我所做过的难度最大的纯模拟题。一般来说，模拟题的题解文字说明都比较少，因为代码具体什么意思大家一般都能看明白，但这道题不太一样，所以我打算写的稍微多一些。

这类长模拟代码看的时间久了对一些变量可能有记忆混淆的事情发生，所以我在主要过程基本没使用简单的单字母或者双字母命名变量，那样会严重丧失可读性。

我们来分析一下题意。

题目已经给出了安排好的工序，而每个工序需要在几号机上完成以及每个工序的时间也给了出来，我们要做的就是合理安排机器的工作，让总的加工时间最短。

按照题意的约定，最短方案有且只有一种，而且不必判断输入的合法性。

我们可以把机器想成若干个「时间线」，在这条时间线上去安排工作。

那么明显的，每个时间段对应的机器就只有俩状态：

1.我在干活

2.我闲着呢

而每一个工件也有自己的加工要求，对于每个工件的工序，总应该先完成小号工序再完成大号工序，也就是必须顺着编号来。

每台机器只能在某时刻进行一种工作，并且后面的安排不能把前面的安排改动掉。

模拟的思想便是从左到右无限扫描整个时间线，然后去尝试插空。

这里有三个辅助数组，如果难理解它们的作用将对我的代码有理解困难。第一个是cnt_now_work_step，它表示当前取到工件的工序数。根据之前输入的workline，每个数都代表一个安排的工序，这个数组就是用来方便后面处理工序的，尽管它名字比较长。第二个是lasttime，它代表某个工件出现的最晚的时间（点），它可以用来方便我们扫描时间线，因为每一个工件必须要完全完成上一道工序后才能接着继续下一道工序。第三个是二维bool数组timeline，它代表某一台机器在某一个时间（点）上是不是正在干活。

有了这三个辅助数组，我们就可以开始按照模拟的思路写代码了。

我们取当前工件nowitem[i]，让cnt_now_work_step[nowitem]++，即代表这个工件的工序+1，用nownumber记录当前工件在当前工序时位于哪一台机器，costtime表示做完这道工序应该花费的时间，lasttime[nowitem]+1便是我们扫描时间线的开端，注意lasttime记录的是时间点。这个for没有终止条件，因为时间轴可能会无穷远。

接下来是关键，判断从这个时间点到干完这道工序，机器有没有空，如果机器表示“我闲着呢”，那么就把这道工序安排给机器的这个时间段，更新timeline和lasttime（lasttime[nowitem] = time + costtime - 1，干完活之后这个工件出现的最晚的时间点应该是这道新工序做完的那一刻），然后更新操作立即break掉，继续扫描时间线。如果机器表示“这个时间段我在干其他活”，那这个任务就不能放在这一段，时间线继续扫描。

这个判断要如何写？我用了一个函数，它传入起始时间点和终止时间点和工件编号，然后去判断它的timeline就好。

循环完所有的工件，整个的时间轴也就确定了。

最后去寻找ans，ans应该等于值最大的那个lasttime（即这个工件最后才做完）。

输出ans即可。

参考代码：

#include <iostream>#define maxn 50using namespace std;int n,m;int ans = 0;int worklist[maxn * maxn];int worknumber[maxn][maxn];int worktime[maxn][maxn];int cnt_now_work_step[maxn];int lasttime[maxn];bool timeline[maxn * maxn][maxn * maxn];bool check_in_line(int begin_time_point,int end_time_length,int workid){    for (int time = begin_time_point; time <= end_time_length;time++)        if (timeline[workid][time])            return false;    return true;    
}int main(){    cin >> m >> n;    for (int i=1;i<=n*m;i++)        cin >> worklist[i];    for (int i=1;i<=n;i++)        for (int j=1;j<=m;j++)            cin >> worknumber[i][j];    for (int i=1;i<=n;i++)        for (int j=1;j<=m;j++)            cin >> worktime[i][j];    for (int i=1;i<=n*m;i++){        int nowitem = worklist[i];
       cnt_now_work_step[nowitem]++;//工序数
       int nownumber = worknumber[nowitem][cnt_now_work_step[nowitem]];        int costtime = worktime[nowitem][cnt_now_work_step[nowitem]];        for (int time = lasttime[nowitem]+1;;time++)//扫描时间轴
           if (check_in_line(time,time+costtime-1,nownumber)){                for (int marktime = time;marktime <= time+costtime-1;marktime++)
                   timeline[nownumber][marktime] = true;
               lasttime[nowitem] = time + costtime - 1;                break;
           }
   }    for (int i=1;i<=n;i++)
       ans = max(ans,lasttime[i]);    cout << ans << endl;    return 0;
}

评论

还没有评论

评论

作者: NewErA 更新时间: 2017-09-07 22:37  在Ta的博客查看  0 

一道很考理解的题目

接下来的2n行，每行都是用空格隔开的m个正整数，每个数不超过20。

这个条件极为关键，我们知道了每个的时间不超过20。 从而用last[n]表示每个工件的当前最后时间，直接从last[i]之后一个个时间点尝试，暴力即可

PS:一开始以为时间很大，写了个记录每个机器当前所有空档的程序，后5个点通过不了，现仍不解，望有大佬能找到反例

正解：

#include <bits/stdc++.h>using namespace std;int n,m,seq[30*30],num[30][30],t[30][30],cnt[30],last[30];
bool used[30][8000];
bool check(int start,int len,int mac)
{
   bool f=true;    for(int i=start;i<start+len;i++) if(used[mac][i]) f=false;    return f;
}int main()
{
   cin >> m >> n;    for(int i=1;i<=n*m;i++) cin >> seq[i];    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++)
           cin >> num[i][j];    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++)
           cin >> t[i][j];    for(int i=1;i<=n*m;i++)
   {
       cnt[seq[i]]++;        int x=seq[i],y=cnt[seq[i]],z=num[x][y];        for(int j=last[x];;j++)
       {            if(check(j,t[x][y],z))
           {                for(int k=j;k<j+t[x][y];k++) used[z][k]=true;                last[x]=j+t[x][y];                break;
           }
       }
   }    int res=0;    for(int i=1;i<=n;i++)
   {
       res=max(res,last[i]);
   }
   cout << res;    return 0;
}

试用于大时间的仅有50分的程序：

#include <bits/stdc++.h>using namespace std;
const int INF=1<<27;
typedef pair<int,int> P;int n,m,seq[30*30],num[30][30],t[30][30],cnt[30],last[30],en[30];
vector<P> spa[30];int main()
{
   cin >> m >> n;    for(int i=1;i<=n*m;i++) cin >> seq[i];    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++)
           cin >> num[i][j];    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++)
           cin >> t[i][j];    for(int i=1;i<=n*m;i++)
   {
       cnt[seq[i]]++;        int g=seq[i],y=cnt[seq[i]],x=num[g][y];        int pos=INF;        for(int j=0;j<spa[x].size();j++)            if(spa[x][j].first+spa[x][j].second-t[g][y]>=last[g])
           {                if(pos==INF) pos=j;                else if(spa[x][j].first<spa[x][pos].first) pos=j;
           }        if(pos==INF)
       {            if(en[x]<last[g])
           {
               spa[x].push_back(P(en[x],last[g]-en[x]));
               en[x]=last[g]+t[g][y];                last[g]=en[x];    
           }            else
           {
               en[x]+=t[g][y];                last[g]=en[x];
           }
       }        else
       {            if(spa[x][pos].first>=last[g])
           {
               spa[x][pos].first+=t[g][y];
               spa[x][pos].second-=t[g][y];                last[g]=spa[x][pos].first;    
           }            else
           {
               spa[x].push_back(P(last[g]+t[g][y],spa[x][pos].first+spa[x][pos].second-last[g]-t[g][y]));
               spa[x][pos].second=last[g]-spa[x][pos].first;                last[g]+=t[g][y];
           }
       }
   }    int res=0;    for(int i=1;i<=m;i++)
   {
       res=max(res,en[i]);
   }
   cout << res;    return 0;
}

评论

还没有评论

评论

作者: 易水寒风 更新时间: 2017-08-22 16:25  在Ta的博客查看  0 

/*

这道题就是一道大模拟，关键在于处理好边界情况（我就被坑了好几次……），

可以借助图片理解，最好自己出个样例手动画一画。

*/

#include <iostream>#include <algorithm>#include <cstdio>#include <cmath>using namespace std;const int maxm=500;int n,m,ans;//n个工件，每个工件都有m道工序int j,k;//j为1到n中的某个数字，为工件号；k为1到m中的某个数字，为工序号int way[maxm];int machine[20][20],timing[20][20];// 哪一个机器到了哪一步，用的时间int step[20];//到了第几个工序 int z[20];//到了第几个位置 struct W{    int kd[maxm];
}work[20];//i个机器,第j个工件 void plan(int x){    int t=timing[x][step[x]],w=machine[x][step[x]];    int s=0,start;    for(int i=z[x];i<=maxm;i++)
   {        if(work[w].kd[i]==0){
           s++;
       }        else{
           s=0;
       }        if(s==t) {
           start=i-t+1;            break;
       }
   }    for(int i=start;i<=start+t-1;i++)
   {
       work[w].kd[i]=x;        //top[x].use[i]=1;
   }step[x]++;z[x]=start+t;
   ans=max(start+t,ans);
}int main (){    scanf("%d%d",&m,&n);    for(int i=1;i<=n;i++)
   step[i]=1;    for(int i=1;i<=n*m;i++)
   {        scanf("%d",&way[i]); //给定的安排顺序
   }    for(int i=1;i<=n;i++)    for(int j=1;j<=m;j++)
   {        scanf("%d",&machine[i][j]); //i个工件的j个工序所使用的机器号
   }    for(int i=1;i<=n;i++)    for(int j=1;j<=m;j++)
   {        scanf("%d",&timing[i][j]); //i个工件的j个工序的加工时间
   }    for(int i=1;i<=n*m;i++)
   {
       plan(way[i]); //给定的安排顺序
   }cout<<ans;    return 0;
}

评论

还没有评论

评论

作者: 快乐船长 更新时间: 2017-08-14 16:34  在Ta的博客查看  0 

这道题，主要是靠我们手动模拟，所以必须要模拟到位各种情况。如果模拟出来了，这道题就很简单了

希望大家不要只抄代码，认真理解代码。

#include<stdio.h>int n,m, order[500], machine[21][21], time[21][21];//          顺序  i工件j工序使用机械       时间 int now[21],    end_[21],    has_used_t[21][500], ans=0;//工件现工序号  现结束时间  i机器j时间是否被占用 int shu_ru(){    int i,j;    scanf("%d%d",&m,&n);    for(i=1;i<=m*n;i++)           scanf("%d",&order[i]);    for(i=1;i<=n;i++)          for(j=1;j<=m;j++)               scanf("%d",&machine[i][j]);    for(i=1;i<=n;i++)          for(j=1;j<=m;j++)                scanf("%d",&time[i][j]);
}int check(int x,int bg,int ed){    int i;       for(i=bg;i<=ed;i++)            if(has_used_t[x][i]) return 0;         return 1;
}int main(){    int i,j,l;
      shu_ru();       for(i=1;i<=m*n;i++)           //工序
      {            int x=order[i];               //提取工件
           int y=machine[x][++now[x]];   //提取加工机器
           int z=time[x][now[x]];        //提取所需时间
           for(j=end_[x];;j++)                   if(check(y,j,j+z-1))      //可插入?
                  {                         for(l=0;l<z;l++)       //记录时段已使用
                              has_used_t[y][j+l]=1;                     if(j+z>ans) ans=j+z;    //更改总时间
                            end_[x]=j+z;       //更改x结束时间
                       break;
                 }
   }    printf("%d",ans);    return 0;
}