HDU 6168 Numbers

題目連結

題目意思

給你兩個序列A,B，序列B中的數是A中任意兩個數的和。現在給出你A,B序列混在一起的數，讓你找出A序列輸出。

解題思路

B序列中的數是A中任意兩個數的和，那麼給定的序列中最小的兩個數一定是A序列中的，最大的兩個數一定是B序列中的，現在就根據A中的兩個數依次找，兩數相加的和是B中的，就用map，每次将兩數的和在map中除去，剩餘的一個加入A中，再一次往後推即可。

代碼部分

#include <bits/stdc++.h>
using namespace std;
const int maxn = ;
typedef long long ll;

ll a[maxn];
int main()
{
    ll num, m;
    while(~scanf("%lld", &m))
    {
        map <ll, ll> M;
        ll min1=,min2=;
        ll n=(sqrt(*m+)-)/;///b序列的長度

        for(ll i=; i<m; i++)
        {
            scanf("%lld",&num);
            if(num<min2)
            {
                min1=min2;
                min2=num;
            }
            else if(num<min1)
            {
                min1=num;
            }
            M[num]++;///将資料全部存在map容器裡
        }
        M[min1] --;
        M[min2] --;
        a[] = min2;///找出最小的兩個數
        a[] = min1;
        ll ans = ;
        while(ans != n - )
        {
            for(ll i = ; i < ans; ++ i)
            {
                M[a[i] + a[ans]] --;
            }
            map<ll, ll>::iterator it = M.begin();
            while(it!= M.end())
            {
                if(it -> second == ll())
                {
                    M.erase(it ++);
                }
                else
                {
                    break;
                }
            }
            a[++ ans] = M.begin() -> first;
            M[a[ans]] --;
        }
        printf("%lld\n",n);
        printf("%lld",a[]);
        for(int i=; i<n; i++)
            printf("% lld",a[i]);
        printf("\n");
    }
    return ;
}