CF 1353D

문제링크

링크텍스트

문제 읽고 드는 생각

$r-l+1$ 홀수 (ood) 일 때 a[$\frac{l+r}{2}$] ,$r-l+1$ 짝수 (even) 일 때 a[$\frac{l+r-1}{2}$] 이다.
$l$ 과 $r$에 대헛 $mid$ 의 값을 가지고 분할하여 0의 연속이 가장 큰 subset을 찾는 것인데 가장 큰 0의 연속 길이를 찾고 만약 0의 연속길이가 같다면 가장 왼쪽부터 시작하는 경우가 우선 된다.
그렇기 때문에 pirority queue를 사용하고 사용자 함수를 이용해서 tuple 첫번째 원소인 길이가 가장 크다면 더 작은 수가 우선시 되게 설정해주었다. 그리고 더 이상 분할 하지 못하게 하는 제어문도 필요했는데 가장 왼쪽의 수 ( $ll$ ) 와 가장 오른쪽의 수 ( $rr$ )가 동일하게 된다면 더이상 분할 하지 못하게 해주었따.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cmath>
#include <numeric>
#include <limits>
#include <sstream>
#include <iomanip>

#define INF 0x3f3f3f3f // 경우에 따라 다르게
// long long 일 1e18

using namespace std;

int t;
int n;
struct cmp
{
    bool operator()(tuple<int, int, int> t1, tuple<int, int, int> t2)
    {
        if (get<0>(t1) == get<0>(t2))
        {
            return get<1>(t1) > get<1>(t2); // 더 작은 수가 앞으로 오게 
        }
        else
        {
            return get<0>(t1) < get<0>(t2);  // 큰게 앞으로 오게 
        }
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> t;

    while (t > 0)
    {
        cin >> n;
        int l, r;
        l = 1;
        r = n;
        vector<int> arr(n + 1, 0);

        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, cmp> pq;
        pq.push({r - l + 1, l, r});
        int cnt = 1;
        // cout << cnt <<"\n";
        while (!pq.empty())
        {
            if (cnt > n)
                break;
            tuple tt = pq.top();
            pq.pop();
            int len = get<0>(tt);
            int ll = get<1>(tt);
            int rr = get<2>(tt);

            //cout << len <<" " <<ll<< " "<< rr <<"\n";
            if (len % 2 == 1)
            {
                int mid = (ll + rr) / 2;
           
                arr[mid] = cnt;

                if (ll != rr)
                {
                    pq.push({mid - ll, ll, mid - 1}); // mid-1-ll+1
                    pq.push({rr - mid, mid + 1, rr}); // rr-(mid+1)+1
                }
            }
            else
            {
                int mid = (ll + rr - 1) / 2;
         
                arr[mid] = cnt;

                if (ll != rr)
                {
                    pq.push({mid - ll, ll, mid - 1});
                    pq.push({rr - mid, mid + 1, rr});
                }
            }

            cnt++;
        }

        for (int i = 1; i <= n; i++)
        {
            cout << arr[i] << " ";
        }
        cout << "\n";

        t--;
    }
}

후기

사용자 비교 함수에 대해서 자세히 알 필요가 있다