两数之和(数学

YudeS · 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[]里

展开上式可以得到

这个略丑， 我们稍加整理

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

且发现每一行，每一列都有一个相同的元素，又由于我们求的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]，找到任意一种成立的方法就可以了；

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

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

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

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

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

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

#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]