CF-div3-611-D. Christmas Trees| bfs

思路

很容易想到bfs，初始时，把这n棵树加入到队列，然后bfs，每次距离+1，vis标记访问过该点，因为bfs保证了最短距离，所以优先到达的优先标记为合法答案。
开始以为会爆，坐标1e-9~1e9，因为要标记嘛开数组肯定要炸；
那就用map标记，就完事了

代码

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

const int maxn = 2e5+10;
int n,m;
ll x[maxn],a[maxn];

struct node{
	ll dis;
	ll pos;
};
queue<node> que;
map<ll,bool> vis;

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) {
		cin>>x[i];
		vis[x[i]] = true;
		que.push({0,x[i]});
	}
	int cnt = 0;
	ll ans = 0;
	while(!que.empty()){
		if(cnt == m) break;
		ll topDis = que.front().dis;
		ll topPos = que.front().pos;
		que.pop();
		if(vis[topPos-1] == false){
			a[++cnt] = topPos-1;
			ans += topDis+1;
			que.push({topDis+1,topPos-1});
			vis[topPos-1] = true;
			if(cnt == m) break;
		}
		if(vis[topPos+1] == false){
			a[++cnt] = topPos+1;
			ans += topDis+1;
			que.push({topDis+1,topPos+1});
			vis[topPos+1] = true;
			if(cnt == m) break;
		}
	}
	cout<<ans<<endl;
	for(int i=1;i<=cnt;i++){
		cout<<a[i]<<" ";
	}
	return 0;
}