11977 Angry Cows (Bronze)

소를 던지면 해당 위치에 있는 건초더미가 폭발하고, 이는 연쇄적으로 범위 1,2,3,,, 이렇게 터진다.

이 때 원코인으로 터트릴 수 있는 가장 많은 건초더미의 수를 출력하면 된다.

처음 던졌을 때 터트릴 건초가 있어야 연쇄작용이 일어나므로 던지는 위치는 xn중에서 고른다.

그리고 범위를 1씩 증가시켜 나가면서 왼, 오른쪽으로 찾아나가면서 최대범위를 구하고

그 범위안에 있는 건초의 개수를 찾으면 된다.

n이 최대 100밖에 안되므로 리니어하게 찾아도 되고 이분탐색으로 찾아도 된다.

난 이분탐색을 사용했다.

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n, a[101];
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) 
        scanf("%d", a + i);
    sort(a, a + n);
    int ans = 1;
    for (int i = 0; i < n; ++i) {
        int l = i, r = i, cnt = 1;
        while (1) {
            int tl = lower_bound(a, a + n, a[l] - cnt) - a;
            if (tl == l) break;
            l = tl;
            cnt++;
        }
        cnt = 1;
        while (1) {
            int tr = lower_bound(a, a + n, a[r] + cnt) - a;
            if (tr >= n || a[tr] > a[r] + cnt) tr--;
            if (tr == r) break;
            r = tr;
            cnt++;
        }
        ans = max(ans, r - l + 1);
    }
    printf("%d\n", ans);
    return 0;
}