[BOJ 11973] Angry Cows (Silver)

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

11973번: Angry Cows (Silver)

Tag : Binary search

 

문제요약

K개의 폭발을 일으켜 모든 건초더미를 없애야하는데 수직선 상의 좌표 x에 폭발을 일으키면 구간 \([x-R,x+r]\)의 건초더미를 없앨 수 있다.

모든 건초더미를 없앨 수 있는 최소 R을 구하라.

 

풀이

전형적인 이분탐색 문제다. 결정 함수를 \(f(R)=[\)폭발의 반경이 R일 때 모든 건초더미를 없앨 수 있다\(]\)라고 정의하면

\(f(R)\)은 monotonic하다. f(R)=1이라면 f(R+1) 또한 가능하기 때문에  어떠한 점을 기준으로 왼쪽은 0이고

그 지점과 오른쪽은 모두 1인데 이 점을 찾는 것이 문제가 요구하는 것이다.

 

이 문제에서 맞은 사람 페이지 1등을 먹어보려고 온갖 짓을 다했다.

 

기존 1등인 jinhan814님은 4ms, 2540kb이었는데 굉장히 빡셌다...

 

1. mmap fastio : (4ms, 2740 kb)

2. 인라인 함수 (람다) : ``

3. 람다를 못믿겠어서 메인에 다 때려박았다.. : ``

4. 컴파일러 최적화를 기대할만한 요소들 삽입 : ``

5. 메모리 절약을 위해 mmap -> syscall : 4ms, 2252kb 1등 갱신

6. fastio의 버퍼 사이즈 조절 : 4ms, 2224kb

7. c로 다시 작성 + quick sort 직접 구현 : 4ms, 1320kb

 

뿌듯

시간복잡도 : \(O(N+logN)\)

 

전체코드

#pragma GCC optimize("Ofast")
#include<stdio.h>
#include<unistd.h>
#include<stdlib.h>

void swap(int *a, int *b) {
	int t = *a;
	*a = *b;
	*b = t;
}

void partition(int*arr, int l, int r, int *pivot) {
	int i, j = l, p = arr[l];
	for (i = l+1; i < r; i++) {
		if (arr[i] < p) {
			j++;
			swap(&arr[i], &arr[j]);
		}
	}
	*pivot = j;
	swap(&arr[l], &arr[*pivot]);
}

void quicksort(int *arr, int l, int r) {
	if (l >= r)return;
	int pivot;
	partition(arr, l, r, &pivot);
	quicksort(arr, l, pivot);
	quicksort(arr, pivot + 1, r);
}

int iptr, left1;
char ibuf[1<<13];
char read_ch() {
    if (iptr >= left1) left1 = read(0, ibuf, sizeof ibuf), iptr = 0;
    if (!left1) return '\n';
    return ibuf[iptr++];
}
int f() {
    int x = 0;
    for (;;) {
        char c = read_ch();
        switch (c) {
            case 48 ... 57: x = x*10 + (c - 48); break;
            default: return x;
        }
    }
    return x;
}

int main(){
    int N=f(),K=f();
    int *v=malloc(sizeof(int)*N);
    for(int i=0;i<N;i++)v[i]=f();
    quicksort(v,0,N);
    int lo=0,hi=1000000001;
    for(;lo+1<hi;){
        int r=(lo+hi)/2;
        int now=v[0]+r,cnt=1;
        int idx=0;for(;idx<N && now+r>=v[idx];++idx);
        for(;idx<N;++cnt){
            now=v[idx]+r;
            for(;idx<N && now+r>=v[idx];++idx);
        }
        if(cnt<=K)hi=r;
        else lo=r;
    }
    printf("%d",hi);
}