題目連結
題意：給出n個點，記為數組a，然後要你構造出m個點，記為數組b，要求這m+n個元素互不相同，同時對于b數組的每個元素，滿足每個點到最近的a數組裡的某個元素距離最近，求最近的距離的和，同時構造出b數組。
思路：很顯然，根據貪心思想，我們的b數組最好的就是在每個a元素的兩端，比如a數組是1 3 6，那麼構造b數組的時候就考慮，1的兩端0，-1，3的兩端2，4，6的兩端5，7，以此類推，這個過程其實就是bfs的過程。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+1;
int n,m;
ll sum=0,a[maxn];
map<ll,ll>vis;
queue<ll>q;
vector<ll>ans;
void bfs()
{
while(m>0)
{
int top=q.front();
q.pop();
if(vis[top-1]==0) {
vis[top-1]=vis[top]+1,sum+=vis[top];
q.push(top-1);m--;
ans.push_back(top-1);
}
if(m==0) break;
if(vis[top+1]==0)
{
vis[top+1]=vis[top]+1,sum+=vis[top];
q.push(top+1);m--;
ans.push_back(top+1);
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%lld",&a[i]),vis[a[i]]=1;
for(int i=1;i<=n;++i) if(!vis[a[i]-1]||!vis[a[i]+1]) q.push(a[i]);
bfs();
printf("%lld\n",sum);
for(int i=0;i<ans.size();++i) printf("%lld ",ans[i]);
}