自动搬运

查看原文

来自洛谷，原作者为

	YudeS 创造1024

搬运于2025-08-24 21:23:21，当前版本为作者最后更新于2019-10-07 20:15:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目描述

我们知道从$n$个非负整数中任取两个相加共有$n*(n-1)/2$个和，现在已知这$n*(n-1)/2$个和值，要求$n$个非负整数。

 

  注意有多组数据

---

我觉得很妙，甚是可以写一篇题解；

我们有$n$个非负整数（就姑且设为$a[1\sim n]$），答案要求又从小到大输出，我们就从人为从小到大求解($a[1]<a[2]<a[3]<a[4]......$)

这就有了以下数对和

$$\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}a[i]+a[j] $$

这就是输入，我们把它们装在数组$sum[]$里

展开上式可以得到

$$a[1]+a[2]\ ,a[1]+a[3]\ ,a[1]+a[4]\ ,a[1]+a[5]\ ...\ a[1]+a[n] $$$$a[2]+a[3]\ ,a[2]+a[4]\ ,a[2]+a[5]\ ...\ a[2]+a[n]$$ $$...$$ $$a[n-1]+a[n]$$

这个略丑， 我们稍加整理

这样子我们可以得到一个倒三角形，

且发现每一行，每一列都有一个相同的元素，又由于我们求的$a[]$单调递增（单调不下降），可知：

每一行，从左到右，值依次递增

每一列，从上到下，值依次递增

元素周期表的感觉

可以进一步推出当前图最小的那个点一定在左上角（<-突破口

 

 

意味着将$sum[]$排个序后，我们知道了最小的$sum(sum[1])$，这其实就是$a[1]+a[2]$

那假如我们现在知道$a[1]$了，那我们也知道$a[2]$了；

我们在$sum[]$中删去$a[1]+a[2]$，那当前的的最小值就是$a[1]+a[3]$了，我们知道$a[1]$，$a[3]$也就知道了；

当前得到了$a[1],a[2],a[3]$，我们删除倒三角形中第二列的数：$a[1]+a[3],a[2]+a[3]$;

现在最小的就是$a[1]+a[4]$了，同理可以得知$a[4]$；

我们发现用这种方法就可以求出所有的元素；

如果还有点不理解的话，可以看看文章底部的模拟；

 

当然这建立在知道$a[1]$的情况下，这样显然可以枚举$a[1]$，找到任意一种成立的方法就可以了；

$a[1]$的取值范围为$[0,(sum[1]/2)]$，因为$a[1]+a[2]=sum[1]\& \&a[1]<=a[2]$

 

操作中涉及到 查询最小值，删除值，可以用$set$；

又想到$sum[]$中也有可能出现重复的值,自然用$multiset$比较保险

这样子枚举$a[1]$的时间是依靠值域的，总共操作的点有$n^2$个，删除的时间复杂度是$log_n$，

所以对于一个数据点的时间复杂度的上界是$O(max_aN^2logN)$；

 

如何处理$impossible$的情况呢，如果我们当前找不到要删除的点，说明当前枚举的$a[1]$不成立，如果一个成立的$a[1]$都找不到的话，就无解了；

 

讲的有些复杂，很多内容可以直接跳过；

$Code$

#include<bits/stdc++.h>
#define mp make_pair
#define ll long long
using namespace std;

int n;
int sum[50];
int a[20];
bool fl;
multiset<int> s;
multiset<int>::iterator it;
inline int read()
{
	int  x=0,fl=1;char st=getchar();
	while(st<'0'||st>'9'){ if(st=='-')fl=-1; st=getchar();}
	while(st>='0'&&st<='9') x=x*10+st-'0',st=getchar();
	return x*fl;
}

inline bool check(int x)
{
	a[1]=x;	//确定a[1] 
	for(int i=2;i<=n;i++)
	{
		a[i]=*s.begin()-a[1];	//确定a[i] 
		for(int j=1;j<i;j++)
		{
			it=s.find(a[j]+a[i]);	
			if(it==s.end())		//当前的a[1]不成立 
				return 0;
			s.erase(it);	 //删除倒三角形中第i列下方的点 
		}
	}
	return 1;
}

int main()
{
	while(~scanf("%d",&n))
	{
		fl=0;	// 记得初始 
		for(int i=1;i<=n*(n-1)/2;i++)
			sum[i]=read();
	
		sort(sum+1,sum+1+n*(n-1)/2);
		
		for(int i=0;i<=(sum[1]/2);i++)
		{
			s.clear();
			for(int j=1;j<=n*(n-1)/2;j++)
				s.insert(sum[j]);		//初始multiset 
			if(check(i))	//有一组解就输出 
			{
				for(int j=1;j<=n;j++)
					printf("%d ",a[j]);
					puts("");
				fl=1;
				break;
			}
		}
		if(!fl)printf("Impossible\n");	//无解 
		
	}
	return 0;
}

这里模拟一下$n=5$的情况，我们已经枚举了$a[1]$，同时得出了$a[2]$