#include<iostream>
#include<vector>
#include<algorithm>
#include<map>

using namespace std;

typedef struct
{
	int kind;
	vector<int> data;
	int flag;
} mole;

int chose(int a, const vector<int>& stamp, map<int, int>& mapkind, mole& comb)
{
	vector<int>::const_iterator it;
	vector<int>::const_iterator it2;
	vector<int>::const_iterator it3;
	vector<int>::const_iterator it4;
	int sum = 0;
	vector<mole> prop;
	for (it = stamp.begin(); it != stamp.end(); ++it)
	{
		if (*it > a)
		{
			break;
		}
		for(it2 = it; it2 != stamp.end(); ++it2)
		{
			sum = *it + *it2;
			if (sum > a)
			{
				break;
			}
			for(it3 = it2; it3 != stamp.end(); ++it3)
			{
				sum = *it + *it2 + *it3;
				if (sum > a)
				{
					break;
				}
				for(it4 = it3; it4 != stamp.end(); ++it4)
				{
					sum = *it + *it2 + *it3 + *it4;
					if (sum > a)
					{
						break;
					}

					if (sum == a)
					{
						mole tmp;
						tmp.flag = 0;
						tmp.kind = 0;
						if (0 != *it)
						{
							tmp.data.push_back(*it);
						}
						if (0 != *it2) 
						{
							tmp.data.push_back(*it2);
						}
						if (0 != *it3) 
						{
							tmp.data.push_back(*it3);
						}
						if (0 != *it4) 
						{
							tmp.data.push_back(*it4);
						}

						//计算kind
						int curvalue = 0;
						int count = 0;
						int kind = 0;
						vector<int>::iterator tmpit;
						for(tmpit = tmp.data.begin(); tmpit != tmp.data.end(); ++tmpit)
						{
							if (*tmpit != curvalue)
							{
								if (0 != curvalue)
								{
									kind = mapkind[curvalue];
									if (1 == count)
									{
										tmp.kind++;
										if(kind > 1)
										{
											tmp.flag = 1;
										}
									}
									else
									{
										tmp.kind += count < kind ? count : kind;
										if((kind > 1) && (count != kind))
										{
											tmp.flag = 1;
										}
									}
								}

								curvalue = *tmpit;
								count = 1;
							}
							else
							{
								count++;
							}
						}
						kind = mapkind[curvalue];
						if (1 == count)
						{
							tmp.kind++;
							if(kind > 1)
							{
								tmp.flag = 1;
							}
						}
						else
						{
							tmp.kind += count < kind ? count : kind;
							if((kind > 1) && (count != kind))
							{
								tmp.flag = 1;
							}
						}

						prop.push_back(tmp);
					}
					
				}
			}
		}
	}
	
	if(prop.empty())
	{
		comb.kind = -1;
		return 0;
	}

	if(1 == prop.size())
	{
		comb.kind = prop[0].kind;
		if(0 == prop[0].flag)
		{
			comb.data = prop[0].data;
		}
	}
	else
	{
		int maxkind = 0;
		vector<mole>::iterator vit;
		for (vit = prop.begin(); vit != prop.end(); ++vit)
		{
			if (vit->kind > maxkind)
			{
				maxkind = vit->kind;
			}
		}

		vector<mole> tmpvm;
		for (vit = prop.begin(); vit != prop.end(); ++vit)
		{
			if (vit->kind == maxkind)
			{
				tmpvm.push_back(*vit);
			}
		}
		if (1 == tmpvm.size())
		{
			comb.kind = tmpvm[0].kind;
			if(0 == tmpvm[0].flag)
			{
				comb.data = tmpvm[0].data;
			}
		}
		else
		{
			prop.swap(tmpvm);
			tmpvm.clear();
			int minstamp = prop[0].data.size();
			for (vit = prop.begin(); vit != prop.end(); ++vit)
			{
				if (vit->data.size() < minstamp)
				{
					minstamp = vit->data.size();
				}
			}

			for (vit = prop.begin(); vit != prop.end(); ++vit)
			{
				if (vit->data.size() == minstamp)
				{
					tmpvm.push_back(*vit);
				}
			}

			if (1 == tmpvm.size())
			{
				comb.kind = tmpvm[0].kind;
				if(0 == tmpvm[0].flag)
				{
					comb.data = tmpvm[0].data;
				}
			}
			else
			{
				prop.swap(tmpvm);
				tmpvm.clear();
				int maxdemo = 0;
				for (vit = prop.begin(); vit != prop.end(); ++vit)
				{
					if (vit->data[vit->data.size() - 1] > maxdemo)
					{
						maxdemo = vit->data[vit->data.size() - 1];
					}
				}

				for (vit = prop.begin(); vit != prop.end(); ++vit)
				{
					if (vit->data[vit->data.size() - 1] == maxdemo)
					{
						tmpvm.push_back(*vit);
					}
				}

				if (1 == tmpvm.size())
				{
					comb.kind = tmpvm[0].kind;
					if(0 == tmpvm[0].flag)
					{
						comb.data = tmpvm[0].data;
					}
				}
				else
				{
					comb.kind = tmpvm[0].kind;
					return 0;
				}

			}
		}
	}

	return 0;
}

int main()
{
	int a;
	while(1)
	{
		vector<int> stamp;
		vector<int> custom;
		while(cin>>a)
		{
			if (0 == a)
				break;
			stamp.push_back(a);
		}
		while(cin>>a)
		{
			if (0 == a)
				break;
			custom.push_back(a);
		}

		map<int, int> mapkind;
		map<int, int>::iterator mit;
		vector<int>::iterator it;
		for (it = stamp.begin(); it != stamp.end(); ++it)
		{
			mit = mapkind.find(*it);
			if (mit == mapkind.end())
			{
				mapkind.insert(make_pair(*it, 1));
			}
			else
			{
				mit->second++;
			}
		}

		
		sort(stamp.begin(), stamp.end());
		unique(stamp.begin(), stamp.end());
		stamp.insert(stamp.begin(), 0);

		map<int, mole> tmpdata;
		
		vector<int> tmpcustom = custom;
		unique(tmpcustom.begin(), tmpcustom.end());
		for (it = tmpcustom.begin(); it != tmpcustom.end(); ++it)
		{
			int total = *it;
			mole comb;
			int iret = chose(total, stamp, mapkind, comb);
			tmpdata.insert(make_pair(total, comb));
		}
		for (it = custom.begin(); it != custom.end(); ++it)
		{
			mole comb = tmpdata[*it];
			cout<<*it<<" ";
			if (-1 == comb.kind)
			{
				cout<<"---- none"<<endl;
			}
			else
			{
				if (0 == comb.data.size())
				{
					cout<<"("<<comb.kind<<"): tie"<<endl;
				}
				else
				{
					cout<<"("<<comb.kind<<"):";
					vector<int>::iterator vitd;
					for (vitd = comb.data.begin(); vitd != comb.data.end(); ++vitd)
					{
						cout<<" "<<*vitd;
					}
					cout<<endl;
				}
			}
		}
	}

	return 0;
}

• Re:为什么总是TLE？ (22) acidsweet 2012-12-13 16:32:55