1283-D, *1800

Problem - D - Codeforces

문제

• $n(1 \leq n \leq 2\cdot 10^{5})$개의 나무가 수직선 위의 서로다른 $x_{i} \in \mathbb{Z}$에 있다
• $m(1 \leq m \leq 2\cdot 10^{5})$명의 사람의 위치 $y_{i} \in \mathbb{Z}$는 다음 조건을 만족해야 한다 
  1. 나무가 있는 정수좌표에는 사람이 있으면 안된다
  2. 한 좌표에는 두명 이상이 있으면 안된다
• 어떤 사람 $y_{i}$의 인접한 나무와의 거리를 $d_{i}$라 할때, $d_{i} = \overset{n}{\underset{j=1}{\text{min}}}|y_{i}-x_{j}|$
  $d_{i}$의 합이 최소가 되도록 사람을 배치할 때의 $\mathrm{Sum(d_{i})}$과 $y_{i}$를 출력하라

 

$O(nlog\ n)$

c++

#include <bits/stdc++.h>
#define endl "\n"
#define ooop(i, n) for(int i = 0; i < n; i++)
#define loop(i, n) for(int i = 1; i <= n; i++)
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int n, m;
    cin >> n >> m;
 
    vector<int> tree(n);
    for(auto& e: tree) cin >> e;
 
    queue<pair<int, int> > q;
    set<int> occupied;
    vector<int> res;
    for(auto coord: tree){
        occupied.insert(coord);
        q.push({coord-1, 1});
        q.push({coord+1, 1});
    }
 
    ll d_sum = 0;
    int cur, dis;
    while(m){
        tie(cur, dis) = q.front(), q.pop();
        if(occupied.find(cur) == occupied.end()){
            d_sum += dis;
            res.emplace_back(cur);
            occupied.insert(cur);
            q.push({cur-1, dis+1});
            q.push({cur+1, dis+1});
            m--;
        }
    }
 
    cout << d_sum << endl;
    for(auto e: res) cout << e << ' ';
 
    return 0;
}cs

참고

안즈와 소소한 취미생활

본 게시물의 코드는 안즈선배님의 도움을 받아 작성한 코드입니다.