[Baekjoon - 21016] Auction Market

난이도: Platinum IV

 

태그

• Segment Tree
• Binary Search (on Segment Tree)

 

풀이

1. 특정 구간 안에서 Bid할 수 있는 물건이 존재하는지 판별해보자.

돈을 \( x \)만큼 가지고 있는 사람이 Bid할 수 있는 물건은, 현재 가격이 \( x \)보다 저렴한 물건들입니다.

 

그럼, \( i \)번째 물건의 현재 가격이 \( A_{i} \)라고 하면,

\( [s, e] \) 구간에서 Bid할 수 있는 물건이 존재하는지 보려면, \( \min\limits_{s \le i \le e} A_{i} \)이 \( x \)보다 작은지 판별하면 됩니다.

min 쿼리는 세그먼트 트리로 잘 처리해주면 되죠.

 

2. 이를 토대로, 어떤 사람이 Bid하는 위치를 찾아보자.

[1]의 아이디어를 잘 사용하면, 이분 탐색을 사용해볼 수 있습니다.

 

어떤 사람이 Bid하는 위치가 \( [s, e] \) 구간으로 고정되어있다면,

중점을 기준으로 아래 두 가지로 나눠볼 수 있습니다.

• \( [s, m] \)에서 Bid할 수 있는 물건이 있다: Bid하는 위치를 \( [s, m] \)으로 변경 후, 이진 탐색을 계속 진행합니다.
• 없다: Bid하는 위치를 \( (m, e] \)로 변경 후, 이진 탐색을 계속 진행합니다.

 

이진 탐색을 \( \min \) 쿼리를 날려가면서 진행해도 되고, Kth Segment Tree 느낌으로 적당히 잘 써서 해도 됩니다.

 

3. Bid한 뒤에는 어떻게 될까?

\( i \)번째 사람이 \( j \)번째 물건에 Bid했다고 합시다.

그럼, \( j \)번째 물건의 가격이 \( B_{i} \)로 변경되고, \( j \)번째 물건은 항상 팔림이 보장되겠죠.

 

이 2개를 Segment Tree의 Update에 적용시키면 됩니다.

 

4. 구현 디테일

경매이기 때문에 기본적으로는 현재 가격보다 더 높은 값을 불러야 하지만,

예외적으로 초기 금액일 때는 초기 금액과 동일한 값을 부를 수 있습니다.

 

하지만 초기 상태를 예외처리하기 귀찮기 때문에, 초기 금액에서 1을 뺀 값을 대신 저장하면

항상 더 높은 금액을 불러야 한다 로 고정할 수 있습니다.

 

5. 코드

const int N = 131072;
pi2 seg[262150];
void upd(int pos, pi2 val){ pos += N-1;
    seg[pos] = val; pos >>= 1;
    while (pos){ seg[pos] = min(seg[pos<<1], seg[pos<<1|1]); pos >>= 1; }
}
int qry(int val){
    int ni = 1; while (ni < N){
        if (seg[ni<<1].fr < val){ ni = ni<<1; } else{ ni = ni<<1|1; }
    }
    return ni-N+1;
}
 
int arr[100020];
 
void Main(){
    int n; cin >> n;
    for (int i = 1; i <= n; i++){ cin >> arr[i]; }
    for (int i = N+n-1; i >= 1; i--){
        if (i >= N){ seg[i] = {arr[i-N+1]-1, 0}; }
        else{ seg[i] = min(seg[i<<1], seg[i<<1|1]); }
    }
    int q; cin >> q; for (int i = 1; i <= q; i++){
        int x; cin >> x; int p = qry(x);
        if (p > n){ continue; } upd(p, {x, i});
    }
    int ans = 0;
    for (int i = 1; i <= n; i++){ ans += (seg[i+N-1].sc > 0); }
    cout << ans;
}