提供一个新思路
这题, 我们假设 n 个数分别为 a1,a2,a3,a4,a5...an, 且对于任意
1<=i<j<=n 满足 ai<aj
而他们两两之和即为输入的各数字, 从中, 我们不难推出对于输入的数字中 (我们把它们按从小到大排序, 分别设为 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<bits/stdc++.h>
- 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('\n');
- }
- 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<zhi-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\n");
- continue;
- }
- }
- return 0;
- }
- /**
- * ┏┓ ┏┓+ +
- * ┏┛┻━━━┛┻┓ + +
- * ┃ ┃
- * ┃ ━ ┃ ++ + + +
- * ████━████+
- * ◥██◤ ◥██◤ +
- * ┃ ┻ ┃
- * ┃ ┃ + +
- * ┗━┓ ┏━┛
- * ┃ ┃ + + + +Code is far away from
- * ┃ ┃ + bug with the animal protecting
- * ┃ ┗━━━┓ 神兽保佑, 代码无 bug
- * ┃ ┣┓
- * ┃ ┏┛
- * ┗┓┓┏━┳┓┏┛ + + + +
- * ┃┫┫ ┃┫┫
- * ┗┻┛ ┗┻┛+ + + +
- */
来源: http://www.bubuko.com/infodetail-2890562.html