main.cpp

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

#include <utility>
#include <list>
#include <vector>
#include <assert.h>
#include <algorithm>
#include <iostream>

using namespace std;

class interval
{
public:
	interval(int begin, int end, int num){
		assert( (end >= begin) && (begin > 0) );
		assert( num > 0);
		assert( end-begin+1 >= num);
        m_begin = begin;//区间开始
		m_end = end;    //区间结束
		m_num = num;    //需要覆盖的点
		m_rest = m_num; //还没有覆盖的点
	}
public:
	int m_begin;
	int m_end;
	int m_num;
	int m_rest;

	bool operator<(interval & inte){
		return m_begin<inte.m_begin;
	}
}; 


class point
{
public:
	bool m_valid;
	int m_active_num;
	int m_erase_num;
	vector< vector<interval>::iterator> m_iterator_vector; 
};

void main(){

    vector<interval> interval_vector;
	interval_vector.reserve(5);

	int inte_num = 0;
	cout<<"please input the number of intervals : ";
	cin>>inte_num;

	for(int i=0;i<inte_num; i++){
		int first=0;
		int last =0;
		int num = 0;
		cout<<"the "<<i<<"th : \n";
		cout<<"first point : ";
		cin>>first;
		cout<<"last point : ";
		cin>>last;
		cout<<"overlap num : ";
		cin>>num;
		cout<<"\n";
		interval inte(first, last, num);
		interval_vector.push_back(inte);
	}

	//interval inte_1(3, 7, 3);
 //   interval_vector.push_back(inte_1);
	//interval inte_2(8, 10, 3);
	//interval_vector.push_back(inte_2);
	//interval inte_3(6, 8, 1);
	//interval_vector.push_back(inte_3);
	//interval inte_4(1, 3, 1);
	//interval_vector.push_back(inte_4);
	//interval inte_5(10, 11, 1);
	//interval_vector.push_back(inte_5);

	sort(interval_vector.begin(), interval_vector.end());

	int begin = interval_vector.front().m_begin;
	int end = begin;
	for(vector<interval>::iterator it = interval_vector.begin(); it != interval_vector.end(); ++it){
        if(end < (*it).m_end) end = (*it).m_end;
	}

	point * point_vector = new point[end-begin+1] ;//<点的位置，对应的区间列表>
	assert(point_vector);
	for(int i=0; i<end-begin+1; i++){
		point_vector[i].m_valid = false;
		point_vector[i].m_active_num = 0;
		point_vector[i].m_erase_num = 0;
	}

	for(vector<interval>::iterator it = interval_vector.begin(); it != interval_vector.end(); ++it){
		for(int i = (*it).m_begin; i<=(*it).m_end; ++i ){
			point_vector[i-begin].m_iterator_vector.push_back(it);
			point_vector[i-begin].m_active_num++;
		}
	}

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	//cout<<"points are ";
	//for(int i=0; i<end-begin+1; i++ ){
	//	cout<<point_vector[i].m_active_num<<" ";
	//}
	//cout<<"\n";   

	//cout<<" intervals are: ";
	//for(vector<interval>::iterator it = interval_vector.begin(); it != interval_vector.end(); ++it){
	//	cout<<(*it).m_rest<<" ";
	//}
	//cout<<"\n";

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



    size_t count = 0;

	for(vector<interval>::iterator it = interval_vector.begin(); it != interval_vector.end(); ++it){

		if( ((*it).m_end - (*it).m_begin + 1) == (*it).m_num  ){
			for(int i = (*it).m_begin; i<=(*it).m_end; ++i ){
				point_vector[i-begin].m_valid = true;
                point_vector[i-begin].m_active_num = 0;
				for(vector< vector<interval>::iterator>::iterator it_i = point_vector[i-begin].m_iterator_vector.begin(); it_i != point_vector[i-begin].m_iterator_vector.end(); ++it_i){
					(*(*it_i)).m_rest--;
					if((*(*it_i)).m_rest == 0) {
						count++;
						for(int i = (*(*it_i)).m_begin; i<=(*(*it_i)).m_end; ++i ){
							if( !point_vector[i-begin].m_valid ) point_vector[i-begin].m_active_num--;
						}
					}
				}
			}
		}

	}

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	//cout<<"points are ";
	//for(int i=0; i<end-begin+1; i++ ){
	//	cout<<" <"<<point_vector[i].m_active_num<<" "<<point_vector[i].m_valid<<"> ";
	//}
	//cout<<"\n";   

	//cout<<" intervals are: ";
	//for(vector<interval>::iterator it = interval_vector.begin(); it != interval_vector.end(); ++it){
	//	cout<<(*it).m_rest<<" ";
	//}
	//cout<<"\n";

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


	while (count < interval_vector.size()) {
		int active_num = 0;
		int index = -1;

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		//cout<<"points are ";
		//for(int i=0; i<end-begin+1; i++ ){
		//	cout<<" <"<<point_vector[i].m_active_num<<" "<<point_vector[i].m_valid<<"> ";
		//}
		//cout<<"\n";   

		//cout<<" intervals are: ";
		//for(vector<interval>::iterator it = interval_vector.begin(); it != interval_vector.end(); ++it){
		//	cout<<(*it).m_rest<<" ";
		//}
		//cout<<"\n";

		///////////////////////////
		for(int i=0; i<end-begin+1; i++){
			if( false == point_vector[i].m_valid ){
				if( active_num < point_vector[i].m_active_num ){
					active_num = point_vector[i].m_active_num;
					index = i;
				}
			}
		}
		assert( (index >= 0) && (active_num>0));

		point_vector[index].m_valid = true;
		for(vector<vector<interval>::iterator>::iterator it_i = point_vector[index].m_iterator_vector.begin(); it_i != point_vector[index].m_iterator_vector.end(); ++it_i){
			(*(*it_i)).m_rest--;
			if((*(*it_i)).m_rest == 0){ 
				count++;
				for(int i = (*(*it_i)).m_begin; i<=(*(*it_i)).m_end; ++i ){
					if( !point_vector[i-begin].m_valid ) point_vector[i-begin].m_active_num--;
				}
			}
		}

	}

////////////////////////////////////////////////////////////////////////////////
//	cout<<"points are ";
//	for(int i=0; i<end-begin+1; i++ ){
//		if(point_vector[i].m_valid) 
//			cout<<i<<" ";
//	}
//	cout<<"\n";   
////////////////////////////////////////////////////////////////////////////////////

	while(true){
		int mini_index = -1;
		size_t mini_erase_num = interval_vector.size()+1;
		for(int i=0; i<end-begin+1; i++ ){
			if(point_vector[i].m_valid  && ( mini_erase_num>=point_vector[i].m_iterator_vector.size() ) ){
                point_vector[i].m_erase_num = 0;
				int erase_num = 0;
				for(vector<vector<interval>::iterator>::iterator it_i = point_vector[i].m_iterator_vector.begin(); it_i != point_vector[i].m_iterator_vector.end(); ++it_i){
					if((*(*it_i)).m_rest<0){
                        erase_num++;
					}else{
						break;
					}
				}
				assert(erase_num <= point_vector[i].m_iterator_vector.size());
				if(erase_num != point_vector[i].m_iterator_vector.size()){
					point_vector[i].m_erase_num = 0;
				}else{
                    point_vector[i].m_erase_num = erase_num;
					mini_erase_num = erase_num;
					mini_index = i;
				}
			}
		}

		if(-1 == mini_index) break;//succeed
        point_vector[mini_index].m_valid = false;
		for(vector<vector<interval>::iterator>::iterator it_i = point_vector[i].m_iterator_vector.begin(); it_i != point_vector[i].m_iterator_vector.end(); ++it_i){
			((*(*it_i)).m_rest)++;
		}  


	}

	////////////////////////////////////////////////////////////////////////////////
	int valid_num = 0;
	cout<<"points are ";
	for(int i=0; i<end-begin+1; i++ ){
		if(point_vector[i].m_valid) {
			cout<<i<<" ";
			valid_num++;
		}
	}
	cout<<"\n";   
	cout<<"size of the set is "<<valid_num<<"\n";
	//////////////////////////////////////////////////////////////////////////////////


}