2466.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Memory:92K  Time:77MS
Language:C++  Result:Accepted

Source 

#include"iostream"
#include"set"

using namespace std;

multiset<int> s;
int sum[100],n,m,max,mins;

bool init()
{
	int i;
	cin>>n;
	if(cin.fail())return 0;

	m=n*(n-1)/2;
	max=-99999999;mins=999999999;
	for(i=0;i<m;i++)
	{
		cin>>sum[i];
		if(max<sum[i])max=sum[i];
		if(mins>sum[i])mins=sum[i];
	}
	
	return 1;
}

int ans[100];
bool doit()
{
	int min,i,j;
	multiset<int>::iterator iter;

	for(ans[0]=mins/2+10;;ans[0]--)
	{
		min=ans[0];
		s.clear();
		for(i=0;i<m;i++)
			s.insert(sum[i]);

		if((*s.begin()-ans[0])*2>max)
			return 0;

		for(i=1;i<n;i++)
		{
			ans[i]=*s.begin()-ans[0];
			
			if(ans[i]<min)break;
			min=ans[i];

			for(j=i-1;j>=0;j--)
			{
				if((iter=s.find(ans[i]+ans[j]))==s.end())break;
				s.erase(iter);
			}

			if(j>=0)break;
		}

		if(i==n)return 1;
	}
}

int main()
{
	int i;
	while(init())
	{
		if(!doit())
		{
			cout<<"Impossible";
		}
		else for(i=0;i<n;i++)
		{
			if(i)cout<<" ";
			cout<<ans[i];
		}
		cout<<endl;
	}

	return 0;
}