sched.cpp

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

#include <stdio.h>
#include <algorithm>
#include <iostream>
using namespace std;

//求两个数的最大值
#define max(x, y) ((x)>(y)?(x):(y))
class Task
{
public:
    int A;
    int B;
    bool operator < (Task q) const//重载"<"
	{
		return A<q.A || A==q.A&&B<q.B;
	}
};

int main()
{
	int i, j,best,tmp_min, n, p, q, current_task_index,index;
	freopen("input.txt","r",stdin);    
	freopen("output.txt","w",stdout);  
	scanf("%d", &n);
	Task *jobs=new Task [n];
	Task *t=new Task [10*n];//用来存放动态规划过程中可能的状态
	Task *tmp_best=new Task [10*n];//保存剪枝剩下的状态
	for (i = 0; i < n; i++) 
		scanf("%d", &jobs[i].A);
	for (i = 0; i < n; i++) 
		scanf("%d", &jobs[i].B);
	tmp_best[0].A = tmp_best[0].B = 0;
	current_task_index = 1;
	for (i = 0; i < n; i++)
	   {
		index= 0;
		//cout<<"i="<<i+1<<endl;
		//cout<<"current_task_index="<<current_task_index<<endl;
		for (j = 0; j < current_task_index; j++)//任务可能的分配情况
		{
			t[index].A = tmp_best[j].A + jobs[i].A;
			t[index].B = tmp_best[j].B;              
			t[index+1].A = tmp_best[j].A;
			t[index+1].B = tmp_best[j].B+ jobs[i].B;
			//cout<<t[index].A<<" "<<t[index].B<<endl;
			//cout<<t[index+1].A<<" "<<t[index+1].B<<endl;
			index+=2;
		}
                
		sort(t, t+index);//先按照A的大小,如果A一样的话,按照B的大小从小到大排好序
		tmp_best[0] = t[0];
		current_task_index = 1; tmp_min = t[0].B;
		//cout<<"剪枝后的状态"<<endl;
		//cout<<t[0].A<<" "<<t[0].B<<endl;
		for (j = 1; j <index; j++)
			if (t[j].B < tmp_min)//不剪枝的条件
			{
				//数组tmp_best[]保存剪枝后剩下的状态
				tmp_best[current_task_index++] = t[j];//current_task_index记录当前剪枝后剩下的状态个数
				//cout<<t[j].A<<" "<<t[j].B<<endl;
				tmp_min = t[j].B;
			}
	   }
	best=INT_MAX;
	//求所有较大值里面的最大值
	for (i = 0; i < current_task_index; i++)
	   {
		j=max(tmp_best[i].A,tmp_best[i].B);//取机器A和机器B中时间较大的
		if (j <best)best=j;
	   }
	printf("%d\n",best);
	delete []tmp_best;
	delete []t;
	delete []jobs;
	return 0;
}