Christmas Trees [Codeforces Round #611 (Div. 3) D]

https://codeforces.com/contest/1283/problem/D

解説

https://codeforces.com/contest/1283/submission/67849985

人を適切に配置する問題であるが、最適解を考えると、木の周りに順番に人を配置していくのがいいだろう。
木を始点にしてBFSをしていくのがいい。
木の座標が大きいので、setとmapで適当にやっていくと通る。

vis[i] := 座標iに到達済み
dist[i] := 座標iでの木からの最短距離

あとは、queueを使ってBFSをする要領で最短距離であるものを選んで行く。

int N, M, A[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> A[i];

    set<int> vis;
    map<int, int> dist;
    queue<int> que;

    rep(i, 0, N) {
        vis.insert(A[i]);
        dist[A[i]] = 0;
        que.push(A[i]);
    }

    ll ans1 = 0;
    vector<int> ans2;
    while (!que.empty()) {
        int cu = que.front(); que.pop();

        if (0 < dist[cu]) {
            ans1 += dist[cu];
            ans2.push_back(cu);
            M--;
            if (M == 0) break;
        }

        rep(d, -1, 2) if (d != 0) {
            int nxt = cu + d;
            if (vis.count(nxt)) continue;
            vis.insert(nxt);
            dist[nxt] = dist[cu] + 1;
            que.push(nxt);
        }
    }

    printf("%lld\n", ans1);
    M = ans2.size();
    rep(i, 0, M) {
        if (i) printf(" ");
        printf("%d", ans2[i]);
    }
    printf("\n");
}