Codeforces Round #550 (Div. 3) D. Equalize Them All

D. Equalize Them All

https://codeforces.com/contest/1144/problem/D

주어진 두 연산을 자세히 보면, i번째 수는 j번째 수와 같아지게 된다는 것을 알 수 있다.

이때, 연산 횟수를 최소화 하려면, 가장 많이 있는 수를 기준으로 연산을 수행하면 된다.

가장 많이 입력된 수를 찾고, 그 index를 중심으로 왼쪽, 오른쪽으로 연산을 진행하자.

루프 돌 때, 기준이 되는 수가 나왔다면 가볍게 넘어가준다.

#include <bits/stdc++.h>
using namespace std;
 
int n;
int arr[200001];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    map<int, int> mp;
    int mx = 0, mxidx = -1;
    
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        mp[arr[i]]++;
        if (mp[arr[i]] > mx) {
            mx = mp[arr[i]];
            mxidx = i;
        }
    }
 
    vector<pair<int, pair<int, int>>> vc;
    int ans = 0;
    for (int i = mxidx + 1; i < n; i++) {
        if (arr[i] != arr[i - 1]) {
            if(arr[i] > arr[i - 1])
                vc.push_back({2, { i + 1, i} });
            else
                vc.push_back({1, { i + 1, i} });
 
            arr[i] = arr[mxidx];
            ++ans;
        } 
    }
    for (int i = mxidx - 1; i >= 0; i--) {
        if (arr[i] != arr[i + 1]) {
            if (arr[i] > arr[i + 1])
                vc.push_back({ 2, { i + 1, i + 2} });
            else
                vc.push_back({ 1, { i + 1, i + 2} });
            arr[i] = arr[mxidx];
            ++ans;
        }
    }
 
    cout << ans << '\n';
 
    for (int i = 0; i < vc.size(); i++) {
        cout << vc[i].first << ' ' << vc[i].second.first << ' ' << vc[i].second.second << '\n';
    }
 
    return 0;
}