Problem


Key Idea

\(headquarters\) ์˜ ์ขŒํ‘œ \(x_0\)์„ \(0\)์œผ๋กœ ๋‘๊ณ ,
๋งŽ์ด ๋ฐฉ๋ฌธํ•ด์•ผํ•˜๋Š” ๊ฑด๋ฌผ์ผ์ˆ˜๋ก \(+1, -1, +2, -2 \cdots\) ์ด๋Ÿฐ ์‹์œผ๋กœ \(headquarters\)์— ๊ฐ€๊น๊ฒŒ ์ง€์œผ๋ฉด ๋œ๋‹ค. \((Greedy)\)

  • Time: \(O(n{\log}n)\)


Implementation

/**
 * written: 2021. 11. 26. Fri. 20:42:25 [UTC+9]
 * jooncco์˜ mac์—์„œ.
 **/
 
#include <bits/stdc++.h>
using namespace std;
 
#define FAST_IO ios_base::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
typedef pair<int,int> ii;
typedef deque<int> di;
typedef deque<ii> dii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ii> vii;
typedef priority_queue<int, vi, less<int> > maxHeap;
typedef priority_queue<int, vi, greater<int> > minHeap;
 
int n,a;
 
void solve() {
    cin >> n;
    vii arr(n);
    for (int i=0; i < n; ++i) {
        cin >> a;
        arr[i]= {a,i}; // { ๋ฐฉ๋ฌธํšŸ์ˆ˜, index } ์ €์žฅ
    }
    sort(arr.begin(),arr.end());
    int x0= 0;
    ll curX= 1, ansDis= 0;
    vl ans(n,1e9);
    // ๋งŽ์ด ๋ฐฉ๋ฌธํ•  ๋นŒ๋”ฉ๋ถ€ํ„ฐ ๊ฐ€๊น๊ฒŒ ์ขŒํ‘œ๋ฅผ ๋ฐฐ์ •
    for (int i=n-1; i >= 0; --i) {
        int visitCnt= arr[i].first;
        int origIdx= arr[i].second;
        ans[origIdx]= curX;
        ansDis += abs(curX)*2*visitCnt;
        if (curX > 0) curX= -curX;
        else curX= -curX+1;
    }
    cout << ansDis << "\n";
    cout << 0;  // ๋ณธ์‚ฌ
    for (int i=0; i < n; ++i) cout << " " << ans[i];    // ๋‚˜๋จธ์ง€
    cout << "\n";
}

int main() {
    FAST_IO;
    int t; cin >> t;
    while (t--) solve();
}

Leave a comment