📝 문제 정보
🧐 관찰 및 접근
- 일단 모두 $P$에 몰아넣거나, $Q$에 몰아넣거나는 가능하니 일단 기본적으로 모든 원소의 합정도는 여유롭게 가능하다.
- 그런데, 모든 수가 같다고 생각해보자. 그러면 모든 수는 $P$와 $Q$에 동시에 속하는데…
- 동시에 속할 수 있는 수를 어떻게 제어할 수 있지?
- 동시에 속한 수가 서로 다른 여러개의 수일 수는 없다.
- 어떤 수와 그 개수를 곱한 값이 최대인 수를 골라서, 맨 뒤로 보내자.
💻 풀이
void solve(){
int N; cin >> N;
map<int, int> mp;
int ans = 0;
rep(i, 0, N){
int x; cin >> x;
mp[x]++;
ans += x;
}
int mxIdx = -1, mxVal = -1;
for(auto [k, v]: mp){
if(k*v > mxVal){
mxVal = k*v;
mxIdx = k;
}
}
ans += mxVal;
vector<int> v1, v2;
for(auto [k, v]: mp){
if(k < mxIdx) rep(i, 0, v) v1.push_back(k);
else if(k > mxIdx) rep(i, 0, v) v2.push_back(k);
}
rrep(i, 0, v2.size()) v1.push_back(v2[i]);
rep(i, 0, mp[mxIdx]) v1.push_back(mxIdx);
cout << ans << '\n';
for(auto x: v1) cout << x << ' ';
}