Codeforces 1419D2 Saga's Birthday (hard version)

문제

https://codeforces.com/problemset/problem/1419/D2

걸린 시간

00 : 20 : 53

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
using namespace std;

int n;
vector<int> a, reorder;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    a.resize(n); reorder.resize(n);
    for(auto& i : a) cin >> i;
    sort(a.begin(), a.end());
    int cnt = 0;
    for(int i = 1; i < n; i += 2){
        reorder[i] = a[cnt];
        cnt++;
    }
    for(int i = 0; i < n; i += 2){
        reorder[i] = a[cnt];
        cnt++;
    }
    int cheap = 0;
    for(int i = 1; i < n-1; i++)
        if(reorder[i-1] > reorder[i] && reorder[i+1] > reorder[i])
            cheap++;
    cout << cheap << "\n";
    for(int i = 0; i < n; i++)
        cout << reorder[i] << " ";
    cout << "\n";
    return 0;
}

easy version 과는 다르게 주어지는 수가 중복될 수 있다. 따라서 구매할 수 있는 ice sphere 의 개수는 재정렬된 배열의 가장자리를 제외한 모든 수들을 앞 뒤의 두 값과 비교하여 세어야 한다.