timetable.cpp

一台精密仪器的工作时间为 n 个时间单位。与仪器工作时间同步进行若干仪器维修程序。一旦启动维修程序

#include <stdlib.h>
#include <iostream.h>
#include <fstream.h>
#include <time.h>

int *worktime=0;
int **repairtime=0;
int n;
int k;
//clock_t f,s;

void readdata(){
	int i=0;
	ifstream ifs("input.txt");
	
	if(!ifs){
		cerr<<"Error:unable to open INPUT.TXT"<<endl;
		exit(1);
	}

	ifs>>n;
	worktime=new int[n];
	for(i=0;i<n;i++){
		worktime[i]=n;
	}

	ifs>>k;
	repairtime=new (int *[k]);
	for(i=0;i<k;i++){
		repairtime[i]=new int[2];
		ifs>>repairtime[i][0];
		ifs>>repairtime[i][1];
	}
	ifs.close();
}

int mintime(){
	int temp;
	int down=0,up=0;
	int x,y;
	int i,j;
	int sign=0;

	while((down<k)&&(up<k)&&(repairtime[up][0]==repairtime[down][0])) up++;
	x=repairtime[down][0];
	for(j=down;j<up;j++){
		y=repairtime[j][1];
		worktime[x+y-2]=y;
	}
	if (up==k) goto out;
	
	for(i=0;i<n;i++){
		x=repairtime[down][0]-1;
		sign=0;
		if ((i<x)&&(worktime[i]!=n)){
			for(j=down;j<up;j++){ 
				y=repairtime[j][1];
				if(x+y-1>=n) y=n-x;
				if (worktime[i]+y<worktime[x+y-1])
					worktime[x+y-1]=worktime[i]+y;
					//cout<<x+y-1<<"=="<<worktime[i]+y<<endl;
					sign=1;
			}
			if (sign=1) worktime[i]=n;
		} else if (i>=x){
			down=up;
			if(down>=k)break;
			while((down<k)&&(up<k)&&(repairtime[up][0]==repairtime[down][0])){
				up++;
			}			
			//cout<<down<<"   "<<up<<endl;
			x=repairtime[down][0]-1;
			if ((i<x)&&(worktime[i]!=n)){
				for(j=down;j<up;j++){
					y=repairtime[j][1];
					if(x+y-1>=n) y=n-x;
					if (worktime[i]+y<worktime[x+y-1])
						worktime[x+y-1]=worktime[i]+y;
						//cout<<i<<"  "<<x+y-1<<"=="<<worktime[i]+y<<endl;
						sign=1;
				}
				if (sign=1)worktime[i]=n;
			}
		}
	}

out:temp=n;
	for(i=0;i<n;i++){
		if (temp>worktime[i]) temp=worktime[i];
	}
	return(temp);
}

void main(){

//	s=clock(); 

	int i;

	readdata();	
	//for(int i=0;i<k;i++){
	//	cout<<repairtime[i][0]<<"   "<<repairtime[i][1]<<endl;
	//}

	ofstream ofs;
	ofs.open("output.txt");
    ofs<<mintime()<<'\n';
	ofs.close();

	delete [] worktime;
	for(i=0;i<k;i++){
		delete [] repairtime[i];
	}
	delete [] repairtime;

//	f=clock();
//	cout<<f-s<<endl;
}