connect.cpp

这是一道NOT高中组的题目,是我学习数据结构时所做练习,其中有一些算法可以一起学习

// connect.cpp : Defines the entry point for the console application.
///////////////////////////////////////////////////
//
// 文 件 名： connect.cpp
// 创 建 者：  刘志祥
// 创建时间:   2003-11-15
// 功能描述:   输入N个整数，连接成一个最大的数
//
///////////////////////////////////////

#include "stdafx.h"
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;



//  比较两个高阶数的大小，这里指两个高价数的位数一样，如不是，就很容易
//  两个高阶数有vector来存放，
bool compare(vector<string> vec1,vector<string> vec2)
{
	string str1,str2;

	for(int i=0;i<vec1.size ();i++)
	{
		str1+=vec1[i];
		str2+=vec2[i];
	}
	if(str1>str2)
		return 1;
	else
		return 0;
}

int main(int argc, char* argv[])
{
	int n;
	int i,j;
	string str[10];
	vector<string> coll,coll1,coll2,coll3;
    cout<<"input number:";
	cin>>n;
	for( i=0;i<n;i++)
	{
		cin>>str[i];
		coll1.push_back (str[i]);
	}
	sort(coll1.begin (),coll1.end (),greater<string>());
	coll.push_back (coll1[0]);
	coll.push_back (coll1[1]);
    coll3.push_back (coll1[1]);
	coll3.push_back (coll1[0]);
	if(compare(coll3,coll))
		coll=coll3;
	for(i=2;i<n;i++)
	{
		coll2=coll;
	   coll.push_back (coll1[i]);
		for(j=0;j<coll2.size ();j++)
		{
			coll2.insert (coll2.begin ()+j,coll1[i]);
			if(compare(coll2,coll)) coll=coll2;
			coll2.erase (coll2.begin ()+j);
		}
	}
	for(i=0;i<coll.size ();i++)
		cout<<coll[i];
	cout<<endl;

	return 0;
}