Christmas Trees

题目描述

There are 𝑛n Christmas trees on an infinite number line. The 𝑖i-th tree grows at the position 𝑥𝑖xi. All 𝑥𝑖xi are guaranteed to be distinct.

Each integer point can be either occupied by the Christmas tree, by the human or not occupied at all. Non-integer points cannot be occupied by anything.

There are 𝑚m people who want to celebrate Christmas. Let 𝑦1,𝑦2,…,𝑦𝑚y1,y2,…,ym be the positions of people (note that all values 𝑥1,𝑥2,…,𝑥𝑛,𝑦1,𝑦2,…,𝑦𝑚x1,x2,…,xn,y1,y2,…,ym should be distinct and all 𝑦𝑗yj should be integer). You want to find such an arrangement of people that the value ∑𝑗=1𝑚min𝑖=1𝑛|𝑥𝑖−𝑦𝑗|∑j=1mmini=1n|xi−yj| is the minimum possible (in other words, the sum of distances to the nearest Christmas tree for all people should be minimized).

In other words, let 𝑑𝑗dj be the distance from the 𝑗j-th human to the nearest Christmas tree (𝑑𝑗=min𝑖=1𝑛|𝑦𝑗−𝑥𝑖|dj=mini=1n|yj−xi|). Then you need to choose such positions 𝑦1,𝑦2,…,𝑦𝑚y1,y2,…,ym that ∑𝑗=1𝑚𝑑𝑗∑j=1mdj is the minimum possible.

Input

The first line of the input contains two integers 𝑛n and 𝑚m (1≤𝑛,𝑚≤2⋅1e51≤n,m≤2⋅1e5) — the number of Christmas trees and the number of people.

The second line of the input contains 𝑛n integers 𝑥1,𝑥2,…,𝑥𝑛x1,x2,…,xn (−1e9≤𝑥𝑖≤1e9−1e9≤xi≤1e9), where 𝑥𝑖xi is the position of the 𝑖i-th Christmas tree. It is guaranteed that all 𝑥𝑖xi are distinct.

Output

In the first line print one integer 𝑟𝑒𝑠res — the minimum possible value of ∑𝑗=1𝑚min𝑖=1𝑛|𝑥𝑖−𝑦𝑗|∑j=1mmini=1n|xi−yj| (in other words, the sum of distances to the nearest Christmas tree for all people).

In the second line print 𝑚m integers 𝑦1,𝑦2,…,𝑦𝑚y1,y2,…,ym (−2⋅1e9≤𝑦𝑗≤2⋅1e9), where 𝑦𝑗yj is the position of the 𝑗j-th human. All 𝑦𝑗yj should be distinct and all values 𝑥1,𝑥2,…,𝑥𝑛,𝑦1,𝑦2,…,𝑦𝑚x1,x2,…,xn,y1,y2,…,ym should be distinct.

If there are multiple answers, print any of them.

Examples

input

Copy

2 6
1 5

output

Copy

8
-1 2 6 4 0 3 

input

Copy

3 5
0 3 1

output

Copy

7
5 -2 4 -1 2 

题意

给定n个圣诞树的坐标，让找出m个人的坐标，使得每一个人到其最近的圣诞树距离之和最小，并输出这些坐标。所有圣诞树和人的坐标两两不能相同。

分析

让每一个圣诞树依次往左右两端一步一步扩展，如果新坐标没有占用，就作为人的坐标。将新坐标再放入队列中继续扩展，直到得到了m个坐标时结束

坑点

由于自己固定思维太严重，一直以为unordered_map很快，吃了大亏，wa12了，后来改成了set就ac了，374ms过了

ac代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;
const int maxn = 1e6+10;
typedef pair<int,int> pii;
int N,M;
int arr[maxn],res[maxn],idx;
long long dis;
set<int> st;

void bfs(){
    queue<pii> q;
    for(int i = 0;i<N;i++) {
        q.push({arr[i],arr[i]});
        st.insert(arr[i]);
    }
    while(!q.empty()){
        pii cur = q.front();q.pop();
        int u = cur.first,v = cur.second;
        if(st.find(v+1) == st.end()){
            dis += abs(v+1-u);
            res[idx++] = v+1;
            st.insert(v+1);
            q.push({u,v+1});
        }
        if(idx >= M) break;
        if(st.find(v-1) == st.end()){
            dis += abs(v-1-u);
            res[idx++] = v-1;
            st.insert(v-1);
            q.push({u,v-1});
        }
        if(idx >= M) break;
    }
}
int main(){
    cin>>N>>M;
    for(int i = 0;i<N;i++) {
        scanf("%d",&arr[i]);
    }
    bfs();
    cout<<dis<<endl;
    for(int i = 0;i<idx;i++){
        printf("%d ",res[i]);
    }
    return 0;
}