思路: 如下 ，从三个小点开始 ，像不像bfs ，没错就是bfs ，拿个map来记录每个点是否有树或者人， 把可以放的位置放进答案容器里就行了。
#include<iostream> #include<cstring> #include<vector> #include<algorithm> #include<queue> #include<map> using namespace std; typedef long long ll; const int N=200010; const int mod = 998244353; map<int,bool>mp; vector<int>res; int a[N]; typedef pair<int,int> pii; queue<pii>Q; int main() { int n,m; cin>>n>>m; int cnt=0; for(int i=0;i<n;i++) { cin>>a[i]; mp[a[i]]=true; Q.push({1,a[i]-1}); Q.push({1,a[i]+1}); } ll rr=0; int maxv=0; while(Q.size()) { auto t =Q.front(); Q.pop(); int loc = t.second; int dis = t.first; if(!mp[loc]) { m--; res.push_back(loc); mp[loc]=true; rr += dis; if(!m) break; Q.push({dis+1,loc+1}); Q.push({dis+1,loc-1}); } } cout<<rr<<endl; for(int i=0;i<res.size();i++) cout<<res[i]<<' '; cout<<endl; return 0; }下面发一份超时代码：
#include<iostream> #include<cstring> #include<vector> #include<algorithm> #include<queue> #include<map> using namespace std; typedef long long ll; const int N=200010; const int mod = 998244353; map<int,bool>mp; vector<int>res[N]; int a[N]; int main() { int n,m; cin>>n>>m; int cnt=0; for(int i=0;i<n;i++) { cin>>a[i]; mp[a[i]]=true; } ll rr=0; int maxv=0; for(int t=1;;t++) { for(int j=0;j<n;j++) { if(!mp.count(a[j]-t)) { res[t].push_back(a[j]-t); mp[a[j]-t]=true; cnt++; rr+=t; } if(cnt>=m) break; if(!mp.count(a[j]+t)) { res[t].push_back(a[j]+t); mp[a[j]+t]=true; cnt++; rr+=t; } if(cnt>=m) break; } if(cnt>=m) { maxv=t; break; } } cout<<rr<<endl; for(int i=1;i<=maxv;i++) for(int j=0;j<res[i].size();j++) cout<<res[i][j]<<' '; cout<<endl; return 0; }这样确实慢 ，做了好多无用功。遍历了好多遍数组，真有你的。
