[SWEA] 8569 개미 관찰

출처: SWEA

Approach

Parametric Search 를 적용하는 문제이다.

[탐색] Parametric Search

 

Lower Bound를 이용하는데 해당 개념에 대해 모른다면 아래 내용도 함께 참고

▶ Binary Search (이분 탐색) 

Binary Search (이분 탐색)

 

① 특정 시점에서 개미들이 부딪히는지 알기 위해서

    이분 탐색으로 "특정 시점"을 추적한다. (완전 탐색하는 경우 TLE)

 

② 특정 시점에서 충돌이 발생하는 확인 → isPossible()

    충돌이 발생하지 않는다면 ① 에서 다른 시점으로 정해서 Try (Parametric Search)

 

③ 충돌 확인

    - 개미들을 모두 이동시킨 후 위치 저장 pos[]

    - 첫번째 개미부터 N번째 개미까지 L[]에 넣어가며, 개미들 위치를 비교한다.

      이때, K 마리 제거한 것을 고려하지 않고 전체 N마리에서 비교하는데 충돌이 발생해도

      문제 내용에서 언급된 "적절한 K 마리 제거"로 cover할 수 있는 수치인지 확인 

---

#include <stdio.h>
#define IMPOSSIBLE -1

const int MAX_N = 2e4 + 2;
const int MAX_X = 1e9 + 1;
struct Ant {
    int x, v;
}arr[MAX_N], trr[MAX_N];
int N, K, TC, liveAntCnt, cnt;
double pos[MAX_N], L[MAX_N], ans;

void mergeSort(int start, int end) {
    // 0. base condition
    if (start >= end) return;
    // 1. divide
    int mid = (start + end) / 2;
    // 2. conquer
    mergeSort(start, mid);
    mergeSort(mid + 1, end);
    // 3. merge
    int i = start, j = mid + 1, k = start;
    while (i <= mid && j <= end) {
        if (arr[i].x < arr[j].x)
            trr[k++] = arr[i++];
        else
            trr[k++] = arr[j++];
    }
    while (i <= mid) trr[k++] = arr[i++];
    while (j <= end) trr[k++] = arr[j++];
    // 4. copy
    for (i = start; i <= end; ++i) {
        arr[i] = trr[i];
    }
}

void input()
{
    scanf("%d %d", &N, &K);
    for (int i = 0; i < N; ++i)
    {
        // 개미 위치와 속력
        scanf("%d %d", &arr[i].x, &arr[i].v);
    }
    liveAntCnt = N - K;
}

bool isPossible(double time) {
    // 개미 이동
    for (int i = 0; i < N; ++i)
    {
        pos[i] = arr[i].x + (time * arr[i].v);
    }
    cnt = 0;
    L[cnt++] = pos[0];
    for (int i = 1; i < N; ++i) {
        // i 번째 개미가 이전 개미보다 뒤에 위치하는 경우
        if (L[cnt - 1] < pos[i])
        {
            L[cnt++] = pos[i];
        }
        // i 번째 개미가 첫번째 개미보다 같거나 앞에 위치하는 경우
        // 속력이 낮아서 이전 개미가 앞지르게 된 경우
        else if (L[0] >= pos[i])
        {
            L[0] = pos[i];
        }
        else
        {
            // 중간영역에 있는 경우 Binary Search.
            int left = 0, right = cnt - 1, mid;
            mid = (left + right) / 2;
            while (left < right)
            {
                if (L[mid] < pos[i])
                {
                    left = mid + 1;
                }
                else
                {
                    right = mid;
                }
                mid = (left + right) / 2;
            }
            L[mid] = pos[i];
        }
    }
    // 충돌되지 않고 살아남은 개미 비교
    return liveAntCnt > cnt;
}

void solve() {
    // 개미 정렬
    mergeSort(0, N - 1);
    // Binary Search (Lower Bound)
    double start = 0, end = MAX_X, mid;
    ans = IMPOSSIBLE;
    while (end - start > 1e-7)
    {
        mid = (start + end) / 2;
        if (isPossible(mid))
        {
            ans = end = mid;
        }
        else
        {
            start = mid;
        }
    }
}

int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d", &TC);
    for (int tc = 1; tc <= TC; ++tc)
    {
        input();
        solve();
        printf("#%d %.6lf\n", tc, ans);
    }
    return 0;
}