开发笔记:题解P1286两数之和

提供一个新思路

这题,我们假设n个数分别为a1,a2,a3,a4,a5...an,且对于任意

1<=i

而他们两两之和即为输入的各数字,从中,我们不难推出对于输入的数字中(我们把它们按从小到大排序,分别设为m1,m2...)

一定满足:m1=a1+a2,m2=a1+a3(我们可以用反证法证明结论)

但m3有两种情况:m3=a1+a4或者m3=a2+a3,我们无法判断,那么,

为什么我们不能把a2+a3的情况排除呢？

所以我们可以这样做: 同样枚举a1(1->m1/2),然后算出a2,a3。这时,我们对a2+a3的数字打个标记,当下次访问到的时候将标记取消说明剩下的数字不是a2+a3,那么,剩下的数的最小的那一个一定是a1+a4!同理我们对a2+a4,a3+a4打标记。。。 最后就能求出所有的a了,如果我们求完了n个数,然而,还有数没被打上标记,就说明此时的a1时错误的我们需要重新枚举。

最后,我们就可以求出答案了~

代码:

#pragma GCC optimize(3)//手动Ox优化
#include
using namespace std;
const int N=1e5+2;
int a[N],tot;
int biao[N],maxe;
int ans[N];
bool F=0;
int n;
inline void print(){//输出答案
for(int i=1;i<=n;++i){
printf("%d ",ans[i]);
}
putchar(‘
‘);
}
inline void dfs(int x){
memset(biao,0,sizeof(biao));
ans[1]=x,ans[2]=a[1]-x,ans[3]=a[2]-x;
biao[ans[2]+ans[3]]++;//标记记得用int,因为可能存在两组数之和相等的情况
int zhi=4;
F=1;//假设这次是正确的
for(int i=3;i<=tot;++i){
if(biao[a[i]]){
biao[a[i]]--;
continue;
}
ans[zhi++]=a[i]-x;
if(zhi>n+1){
F=0;//本次答案错误
return;
}
for(int j=2;j-1;++j){
if(ans[zhi-1]+ans[j]>maxe){//如果和大于最大值,肯定错误,跳过
F=0;//本次答案错误
return;
}
biao[ans[zhi-1]+ans[j]]++;//打上标记
}
}
}
int main(){
while(~scanf("%d",&n)){
tot=n*(n-1)/2,maxe=0;
for(int i=1;i<=tot;++i){
scanf("%d",&a[i]);
maxe=maxe>a[i]?maxe:a[i];//求最大值
}
sort(a+1,a+tot+1);//排个序~
bool flag=0;
for(int i=1;i<=a[1]/2;++i){
dfs(i);
if(F){
flag=1,F=0;//找到正确答案,F记得清零
print();//输出
break;
}
}
if(!flag){
printf("Impossible
");
continue;
}
}
return 0;
}
/**
*　　┏┓　　　┏┓+ +
*　┏┛┻━━━┛┻┓ + +
*　┃　　　　　　　┃
*　┃　　　━　　　┃ ++ + + +
* ████━████+
* ◥██◤　◥██◤ +
*　┃　　　┻　　　┃
*　┃　　　　　　　┃ + +
*　┗━┓　　　┏━┛
*　　　┃　　　┃ + + + +Code is far away from 　
*　　　┃　　　┃ + bug with the animal protecting
*　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug　
*　　　┃ 　　　　　　 ┣┓
*　　 ┃ 　　　　　 　┏┛
*　 ┗┓┓┏━┳┓┏┛ + + + +
*　　　　┃┫┫　┃┫┫
*　　　　┗┻┛　┗┻┛+ + + +
*/