求调思路!(带注释)
查看原帖
求调思路!(带注释)
1284815
canwen楼主2024/5/25 17:13
#include<iostream>
#include<cstring>
using namespace std;
int n,m,anpai[900],work[30][30],done[30][30],timee[30][30],ans,notdo[30];
//n个工件,m个机器,ans表示答案 
//anpai[]为安排顺序
//work[][]表示每一道工序的由哪一个机器来做
//done[][] 完成状态,1完成,0没完成 
//timee[][]表示每道工序的时间 
//notdo[]表示机器是否在工作,1为是,0为否 
int main(){
	cin>>m>>n;
	for(int i=1;i<=n*m;i++) cin>>anpai[i];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>work[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>timee[i][j];
	//以上为读入
	 int x,y,dotime;
	//x表示第x个工件,y表示第y道工序,dotime表示这个工序的花时 
	for(int i=1;i<=n*m;i++){
		//枚举各个安排工序 
		x=anpai[i];//第x个工件
		for(y=1;y<=m;y++){
			//按照题意枚举需要加工第几个 工序 了
			 
			if(done[x][y]==0){//表示这一个 工序 没完成 
				
				memset(notdo,0,sizeof(notdo));//初始化每个机器都不在工作 
				 
				done[x][y]=1;//这个安排完成 
				notdo[ work[x][y] ]=1;//负责这个工序的机器工作状态更新为:正在工作 
				dotime=timee[x][y];//这个工序的时长 
				//测试用的,求dalao 调试QWQ 
		    //	 cout<<x<<" "<<y<<" "<<dotime<<endl;//测试,输出:第x个工件,第y道工序没完成,花时dotime 
				for(int xx=1;xx<=n;xx++){
					//枚举每个工件以及对应的工序 
					for(int yy=1;yy<=m;yy++){
						 
						if(done[xx][yy-1]==0&&yy>1) break;//上一个工序都没完成,那这个工序肯定不能完成 
						if(timee[xx][yy]<=dotime&&notdo[ work[xx][yy] ]==0){
							//主要思路:看看第xx个工件第yy道工序所花的时间是否小于dotime,可以的话说明可以一起完成 
							done[xx][yy]=1;//完成 
							notdo[ work[xx][yy] ]==1;//这个机器正在工作 
						}
					}
				}
				
				ans+=dotime;//加入dotime 
				
				break;//找到一个工序没完成就完成了这一个安排,不用继续枚举
				 
			}
		}
	}
	cout<<ans<<endl;//输出用时 
	return 0;
}

10pts

建议dalao复制到dev去看,比较方便

bug错就错在我的贪心策略,只要<=dotime才可以加工,样例的2-2和3-2工序的加工就矛盾了

可是想不出别的策略了,这个思路还有救吗?!

2024/5/25 17:13
加载中...