missilepro.cpp

acm防御导弹问题详细解答

#include <iostream>
#include <ctime>
#include <cstdlib>

#include "missilePro.h"
using namespace std;


void MissilePro::PrintResl()
{
	if (m_A)
		delete []m_A;
	if (m_Res)
		delete []m_Res;
	if (m_Idx)
		delete []m_Idx;

	m_A = new int[m_N];
	m_Res = new ReservedState[m_N];
	m_Idx = new int[2 * m_N - 1];
	if (!(m_A && m_Res && m_Idx)){
		std::cout<<"fata err, no enough mem! exit..."<<std::endl;
		exit(-1);
	}
	for (int i = 0; i < 2 * m_N - 1; i++){
		m_Idx[i] = -1;
	}

	if (m_manual_input){
		inputArray();
	}else
		generate();

	solve();
	std::cout<<"this is misile defence system can intercept "<<m_numb<<" misiles"<<std::endl;
	std::cout<<"in order to intercept all misiles, we need "<<m_nb_eq<<" such systems"<<std::endl;
}

void MissilePro::generate()
{
	srand((unsigned int )time(NULL));
	for (int i = 0; i < m_N; i++){
		m_A[i] = (int)((float)m_N * rand() / RAND_MAX);
	}
}
void MissilePro::inputArray()
{
	m_N = 7;
	std::cout<<"intput "<<m_N<<" integers"<<std::endl;
// 	for (int i = m_N - 1; i >= 0; i--){
// 		cin>>m_A[i];
// 	}
	m_A[m_N - 1] = 300;
	m_A[m_N - 2] = 250;
	m_A[m_N - 3] = 275;
	m_A[m_N - 4] = 252;
	m_A[m_N - 5] = 200;
	m_A[m_N - 6] = 138;
	m_A[m_N - 7] = 245;
	for (int i = 0; i < m_N; i++){
		std::cout<<m_A[i]<<"   ";
	}
	std::cout<<std::endl;
}

void MissilePro::solve()
{
	bool finished = false;
	bool *solved = new bool[m_N];
	int len = 0;
	int start_idx = 0;

	if (!solved){
		std::cout<<"fata err, no enough mem! exit..."<<std::endl;
		exit(-1);
	}
	m_nb_eq = 0;
// 	len = 1;
// 	m_Res[0].m_data = m_A[0];
// 	m_Res[0].m_idx = 0;
// 	m_Idx[0] = 0;
	for (int i = 0; i < m_N; i++){
		solved[i] = false;
	}
	while (!finished){
		len = 0;
		m_nb_eq++;
		finished = true;
		for (int i = 0; i < m_N; i++){
			if (!solved[i]){
				finished = false;
// 				solved[i] = true;
				int idx_pre = binary_search(m_Res, m_A[i], len - 1);
				if (idx_pre < len - 1){
					if (m_Res[idx_pre].m_data > m_A[i]){
						m_Res[idx_pre].m_data = m_A[i];
						m_Res[idx_pre].m_idx = i;
					}
				}else if (idx_pre == len - 1){
					if (m_Res[idx_pre].m_data > m_A[i]){
						m_Res[idx_pre].m_data = m_A[i];
						m_Res[idx_pre].m_idx = i;
						for (int j = 0; j < len; j++){
							m_Idx[start_idx + j] = m_Res[j].m_idx;
						}
					}else{
						m_Res[len].m_data = m_A[i];
						m_Res[len].m_idx = i;
						m_Idx[start_idx + len] = i;
						len++;
					}
				}else{
					m_Res[idx_pre].m_data = m_A[i];
					m_Res[idx_pre].m_idx = i;
					m_Idx[start_idx + idx_pre] = i;
					len++;
				}
			}
		}
		if (!m_get_maxsub){
			m_get_maxsub = true;
			m_numb = len;
		}
		for (int i = 0; i < len; i++){
			solved[m_Idx[start_idx + i]] = true;
		}
		start_idx += len + 1;
	}
	m_nb_eq--;
	delete []solved;
}

unsigned int MissilePro::binary_search(const ReservedState *m_Res,const int e, const int last_idx)const
{
	int l, r, m;
	l = 0;
	r = last_idx;
	while (l <= r){
		m = (int)((l + r) /  2);
		if (m_Res[m].m_data < e)
			l = m + 1;
		else
			r = m - 1;
	}
	return l;
}

void MissilePro::PrintAllResl()
{
// 	int cnt = 0;
	int nb_systems = 1;
	std::cout<<"system "<<nb_systems<<" : ";
	for (int i = 0; i < 2 * m_N - 1; i++){
		if (-1 != m_Idx[i]){
			std::cout<<m_A[m_Idx[i]]<<"   ";
		}else{
			std::cout<<std::endl;
			nb_systems++;
// 			cnt++;
			if(nb_systems <= m_nb_eq)
				std::cout<<"system "<<nb_systems<<" : ";
			else
				break;
		}
	}
}

void MissilePro::PrintArray()
{
	for (int i = 0; i < m_N; i++){
		std::cout<<m_A[i]<<"   ";
	}
	std::cout<<std::endl;
}
/**
* test procedure
*/
int main(int argc, char **argv)
{
	MissilePro instance;
	instance.SetN(20);
	instance.SetManualInput(false);

	instance.PrintResl();
	instance.PrintAllResl();
	instance.PrintArray();

	return 0;
}