줄 세우기 (백준 2465)

안녕하세요. 오늘은 줄을 세울 거예요.

문제

https://www.acmicpc.net/problem/2465

아이디어

가장 뒤에 있는 사람의 S값: 자신보다 작은 사람의 수 이므로 그 수 +1번째 사람을 배치해주면 됩니다.
가장 뒤에서 두번째에 있는 사람의 S값: 가장 뒤에 있는 사람을 제외하고 자신보다 작은 사람의 수 이므로 그 수 +1번째 사람 (가장 뒤에 사람 제외)을 배치해주면 됩니다.
즉, 맨 뒤에서 부터 찾아보면서 키가 S[idx]+1번째인 사람을 찾아서 배치하고 없애주면 됩니다.

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

ll tree[404040] = { 0 };
ll init(ll s, ll e, ll node)
{
    if (s == e) return tree[node] = 1;
    ll mid = (s + e) / 2;
    return tree[node] = init(s, mid, node * 2) + init(mid + 1, e, node * 2 + 1);
}
ll find(ll s, ll e, ll node, ll num) //자신의 앞에 num개의 1 (합이 num)이도록 idx찾기
{
    if (s == e) return s;
    ll mid = (s + e) / 2;
    if (tree[node * 2] <= num) //오른족에 정답이 있다면
        return find(mid + 1, e, node * 2 + 1, num - tree[node * 2]);
    else //왼쪽에 정답이 있다면
        return find(s, mid, node * 2, num);
}
void change(ll s, ll e, ll node, ll idx) //idx번지에 1빼주기
{
    if (e < idx || idx < s) return;
    tree[node]--;
    if (s == e) return;
    ll mid = (s + e) / 2;
    change(s, mid, node * 2, idx);
    change(mid + 1, e, node * 2 + 1, idx);
}

ll Ans[101010] = { 0 };
int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N, i, x;
    vector <ll> height, order;
    height.push_back(-1);
    order.push_back(-1); //인덱스 1부터 시작하기

    cin >> N;
    for (i = 0; i < N; i++)
    {
        cin >> x;
        height.push_back(x);
    }
    sort(height.begin(), height.end());
    for (i = 0; i < N; i++)
    {
        cin >> x;
        order.push_back(x);
    }

    init(1, N, 1);
    for (i = N; i >= 1; i--)
    {
        ll idx = find(1, N, 1, order[i]);
        Ans[i] = height[idx];
        change(1, N, 1, idx);
    }
    for (i = 1; i <= N; i++)
        cout << Ans[i] << "\n";
}

감사합니다.