44. 마구간 정하기 (이분검색 응용 : 결정 알고리즘)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int a[200001];
int main()
{
    //   freopen("input.txt", "rt", stdin);

    int n, c, lt = 2147000000, rt = -2147000000, mid, i, tmp = 0, max = -2147000000, j, ctmp;

    scanf("%d %d", &n, &c);

    vector<int> x;
    for (i = 0; i < n; i++)
    {
        scanf("%d", &tmp);
        if (rt < tmp)
            rt = tmp;
        x.push_back(tmp);
    }

    sort(x.begin(), x.end());
	lt = 1;
    mid = (lt + rt) / 2;
    ctmp = c - 1; //시작점에 무조건 말 한마리를 배치했다고 가정

    while (lt <= rt)
    {
        ctmp = c - 1;
        mid = (lt + rt) / 2;
        for (i = 0; i < n; i++)
        {
            for (j = i + 1; j < n; j++)
            {
                if (x[j] - x[i] >= mid)
                {
                    i = j - 1;
                    ctmp--;
                    break;
                }
            }

            if (ctmp == 0)
            {
                break;
            }
        }

        if (ctmp == 0)
        {
            lt = mid + 1;
            if (max < mid)
                max = mid;
        }
        else
            rt = mid - 1;
    }

    printf("%d", max);

    return 0;
}

1. 43번 문제와 크게 다를 것 없는 문제지만 가능을 판단하는 방법을 너무 복잡하게 생각했었다. 최적의 답을 구하는 것이 아닌 가능 불가능을 판단하는 것이므로 너무 복잡하게 생각하지 말자..
2. lt를 좌표의 최솟값으로 초기화했었는데 반례가 있었다. lt와 rt의 범위 설정을 신중하게 해야 할 것 같다.

---

동적 배열 할당을 이런 식으로도 한다.

vector <int> x; 와의 차이점은 vector 배열은 메모리를 추가로 계속 늘려줄 수 있지만, 이 방식은 한번 할당하면 메모리를 추가 할당해줄 수 없고 사용이 끝나면 메모리 해제를 해줘야 한다는 점.

    int *x = new int[n + 1];
    sort(x + 1, x + n + 1);
    delete[] x;