題目連結
題目意思
給你兩個序列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 ;
}