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