Codeforces Round #611 (Div. 3) D

There are n">nn Christmas trees on an infinite number line. The i">ii -th tree grows at the position xi">xixi . All xi">xixi 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">mm people who want to celebrate Christmas. Let y1,y2,…,ym">y1,y2,…,ymy1,y2,…,ym be the positions of people (note that all values x1,x2,…,xn,y1,y2,…,ym">x1,x2,…,xn,y1,y2,…,ymx1,x2,…,xn,y1,y2,…,ym should be distinct and all yj">yjyj should be integer). You want to find such an arrangement of people that the value ∑j=1mmini=1n|xi−yj|">∑j=1mmini=1n|xi?yj|∑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">djdj be the distance from the j">jj -th human to the nearest Christmas tree (dj=mini=1n|yj−xi|">dj=mini=1n|yj?xi|dj=mini=1n|yj?xi| ). Then you need to choose such positions y1,y2,…,ym">y1,y2,…,ymy1,y2,…,ym that ∑j=1mdj">∑j=1mdj∑j=1mdj is the minimum possible.

Input

The first line of the input contains two integers n">nn and m">mm (1≤n,m≤2⋅105">1≤n,m≤2?1051≤n,m≤2?105 ) — the number of Christmas trees and the number of people.

The second line of the input contains n">nn integers x1,x2,…,xn">x1,x2,…,xnx1,x2,…,xn (−109≤xi≤109">?109≤xi≤109?109≤xi≤109 ), where xi">xixi is the position of the i">ii -th Christmas tree. It is guaranteed that all xi">xixi are distinct.

Output

In the first line print one integer res">resres — the minimum possible value of ∑j=1mmini=1n|xi−yj|">∑j=1mmini=1n|xi?yj|∑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">mm integers y1,y2,…,ym">y1,y2,…,ymy1,y2,…,ym (−2⋅109≤yj≤2⋅109">?2?109≤yj≤2?109?2?109≤yj≤2?109 ), where yj">yjyj is the position of the j">jj -th human. All yj">yjyj should be distinct and all values x1,x2,…,xn,y1,y2,…,ym">x1,x2,…,xn,y1,y2,…,ymx1,x2,…,xn,y1,y2,…,ym should be distinct.

If there are multiple answers, print any of them.

一开始理解错题面了，用中位数思路写了一通发现连样例都过不了。这个题的意思是确定n个的位置(人和人，人和树的位置不能有重合)，使每个人距离最近的圣诞树的距离的和最小。首先想到把人安排在圣诞树两边(人的位置为树的位置+-1)，两边如果被占据的话继续往两边移。因为题目求的是和最小，容易想到bfs的思想(搜到终点能保证最小),所以在此处利用bfs，并利用map来存储当前位置到最近的树的距离。首先把所有树的坐标扔进队列。从队列取数后，先判断这个位置是否为空位置：if(d[temp]!=0) 为空的话（即字典里没有过这个键对）直接扔进存最终答案的vector里，更新总距离。然后判断这个位置加减1后如果仍然没出现在字典里，把这个位置的距离更新，扔进队列里。循环结束的条件是vector的大小等于m。最终输出就可以了。

(第一次写博客，写的不好还请见谅

#include
using namespace std;
int n,m;
int x[200005]={0};
    vector<int>v;
    queue<int>q;
    map<int,int>d;
int main()
{
    cin>>n>>m;
    int i;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&x[i]);
        q.push(x[i]);
        d[x[i]]=0;
    }
    long long tot_dis=0;
    int cnt=0;
    while(!q.empty())
    {
        if(v.size()>=m)break;
        int temp=q.front();
        q.pop();
        if(d[temp]!=0)
        {
            tot_dis+=d[temp];
            v.push_back(temp);
        }
        if(d.count(temp-1)==0)
        {
            d[temp-1]=d[temp]+1;
            q.push(temp-1);
        }
        if(d.count(temp+1)==0)
        {
            d[temp+1]=d[temp]+1;
            q.push(temp+1);
        }
        
    }
    cout<endl;
    int j;
    for(j=0;j)
    {
        cout<' ';
    }
    return 0;
}