main.cpp

全国高校BBS程序开发大赛赛题－算法项目

#include <iostream>
#include <vector>
#include <algorithm>
#include <assert.h>
#include <math.h>
#include <time.h>

using namespace std;


int MinDeadLine(vector<int> & task_vector, int deadline, vector< vector<int> > * task_schedule, int & end_time);

void print_group(const vector< pair<int, vector< int > > > &  group, const size_t water_num, vector<int> & task_vector){
	assert(0 <= group.size());

	cout<<"\n total time ="<<(group[0]).first<<"\n  the schedule is:\n";
	for(size_t i=0; i<water_num; i++){
		cout<<"the "<<i<<"th : ";
		for(size_t j=i; j<group[0].second.size(); j+=water_num){
			int index = ((group[0]).second)[j];
			assert(index>=-1 && index<=((int)task_vector.size()));

			if(-1 != index) cout<<task_vector[index]<<"  ";
		}
		cout<<"\n";
	}
}


bool compare(int & right, int & left){
	return (right >= left);
}

void main(int argc, char * argv[]){
    
	//vector<int>  task_vector;

	//task_vector.push_back(44);
	//task_vector.push_back(24);
	//task_vector.push_back(24);
	//task_vector.push_back(22);
	//task_vector.push_back(21);
	//task_vector.push_back(17);
	//task_vector.push_back(8);
	//task_vector.push_back(8);
	//task_vector.push_back(6);
	//task_vector.push_back(6);

	int water_num = 3  ;
	cout<<"please input the number of water source provided : ";
	cin>>water_num;



	int task_num = 10;
	cout<<"please input the number of tasks : ";
	cin>>task_num;

	vector<int>  task_vector;
	for(int i=0; i<task_num; i++){
		int tt;
		cout<<"please input the time needed by the "<<i<<"th task : ";
		cin>>tt;
		task_vector.push_back(tt);
	}



	vector< vector<int> > * task_schedule_old = NULL;
	vector< vector<int> > * task_schedule_new = new vector< vector<int> >;
	
    assert( task_vector.size() > 0 );

	sort(task_vector.begin(),task_vector.end(),compare);

	int time_sum = 0;
	int ave_time = 0;
	int max_time = 0;
	for(vector<int>::iterator it = task_vector.begin(); it != task_vector.end(); ++it){
		assert( (*it)>0 );
        time_sum += (*it);
		max_time = max( max_time, (*it) );
	}
	ave_time = int ( ceil( (float)time_sum / water_num ) );
    
	int low_bound = max(ave_time, max_time);
	int up_bound = max( 2*ave_time, max_time);
	int mid_bound = 0;

	int new_end_time = up_bound;
	int old_end_time = up_bound;

	const int LOOP_NUM = 40;

	for(int i = 0; i < LOOP_NUM; i++){

        mid_bound = int( ( low_bound + up_bound)/2 );
		if(mid_bound == up_bound || mid_bound ==low_bound) break;

		//cout<<"up_bound = "<<up_bound<<" low_bound = "<<low_bound<<" mid_bound= "<<mid_bound<<endl;

		if( MinDeadLine( task_vector, mid_bound, task_schedule_new, new_end_time ) <= water_num){
			up_bound = mid_bound;
			if( (new_end_time < old_end_time) || (NULL == task_schedule_old) ){
				if( NULL != task_schedule_old) delete task_schedule_old;
                task_schedule_old = task_schedule_new;
				task_schedule_new = new vector< vector<int> > ;
				old_end_time = new_end_time;
			}
		} else {
			low_bound = mid_bound;
		}		
        
	}

	if( NULL == task_schedule_old ){
		cout<<"no feasible schedule"<<endl;
	} else{	 
		cout<<"the optimal deadline is "<<old_end_time<<endl;
		int i = 0;
		for(vector< vector<int> >::iterator i_it = task_schedule_old->begin(); i_it != task_schedule_old->end(); ++i_it ){
			cout<<"the "<<i<<"th : ";
			for( vector<int>::iterator j_it = (*i_it).begin(); j_it != (*i_it).end(); ++j_it){
				cout<<(*j_it)<<" ";
			}
			cout<<endl;
			++i;
		}
	}

	//////////////////////////////////////////////////////////////////////////


    
	if(NULL != task_schedule_old) 
		delete task_schedule_old;
	if(NULL != task_schedule_new)
		delete task_schedule_new;
	
}



int MinDeadLine(vector<int> & task_vector, int deadline, vector< vector<int> > * task_schedule, int & end_time){

	assert( (deadline>0) && (NULL != task_schedule));
	task_schedule->clear();

	int need_water_num = 0;
	int index = 0;

	vector<int> remain_time;
	remain_time.reserve( task_vector.size() );

	bool insert_falg = false;
	for(vector<int>::iterator it = task_vector.begin(); it != task_vector.end(); ++it){
		assert( ( (*it) > 0) && (deadline >= (*it)) );
		insert_falg = false;

		for(size_t i = 0; ( i < remain_time.size() ) && (!insert_falg) ; i++){
			if( remain_time[i] >= (*it) ){
				remain_time[i] -= (*it);
				(*task_schedule)[i].push_back( (*it) );
				insert_falg = true;
			}
		}

		if( !insert_falg ){
			remain_time.push_back(deadline - (*it) );
			vector<int> new_vector;
			new_vector.push_back( (*it) );
			task_schedule->push_back(new_vector);
			int int_1 = task_schedule->size();
			int int_2 = remain_time.size();
			assert( task_schedule->size() == remain_time.size() );
			insert_falg = true;
		}
	}

	vector<int>::iterator min_remain_it = min_element(remain_time.begin(), remain_time.end());
	end_time = deadline - (*min_remain_it) ;

	need_water_num = remain_time.size();

	return need_water_num;
}