154.ホタル

白駿

1. Python

部分マージ

"""
author : Park Min Hyeok
github : https://github.com/m1nnh
e-mail : alsgur9784@naver.com

title : 개똥벌레
description : 부분합
"""

N, H = map(int, input().split())
Cave = [int(input()) for _ in range(N)]

A = [0] * (H + 2)
B = [0] * (H + 2)
result = [0] * (H + 2)


for i in range(N):
    h = Cave[i]
    if i % 2 == 0:
        B[h + 1] += 1
    else:
        A[H - h] += 1

for i in range(2, H + 1):
    B[i] += B[i - 1]

for i in range(H, -1, -1):
    A[i] += A[i + 1]


for i in range(1, H + 1):
    result[i] = A[i] + B[i]

print(N - max(result), result.count(max(result)))

リファレンス

地面から天井方向に1の高さを増やし、衝突の数を数えます.
1)タケノコの場合,タケノコの高さより1高い場所では該当するタケノコに遭遇しないため,衝突回数は1減少する.
2)鍾乳石については、h - 종유석よりも長さが1よりも高いところで鍾乳石に衝突するため、衝突数は1増加する.
3)1)アトリビュートを高さごとに変更すると、アレイに新しい障害物と衝突の度合いが格納されます.
4)2)で求めた配列で0〜hまでの累積和を求め,最小衝突値とその区間個数を求めた.

バイナリナビゲーション+ソート

リファレンス

n, h = map(int, input().split())

down = []
up = []
for i in range(n):
    if i % 2 == 0:
        down.append(int(input()))
    else:
        up.append(int(input()))

down.sort()
up.sort()

min_count = n
range_count = 0


def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2

        if array[mid] < target:
            start = mid + 1
        else:
            end = mid - 1

    return start


for i in range(1, h + 1):
    down_count = len(down) - binary_search(down, i - 0.5, 0, len(down) - 1)
    top_count = len(up) - binary_search(up, h - i + 0.5, 0, len(up) - 1)

    if min_count == down_count + top_count:
        range_count += 1
    elif min_count > down_count + top_count: # 현재 범위가 새로운 최소 값이면
        range_count = 1
        min_count = down_count + top_count

print(min_count, range_count)

障害物が設置された穴の中をホタルが飛んでいて、穴の高さが6の場合、ホタルが飛んだ高さが3の場合、下から高さが2~3(2.5と考えれば簡単)の区間を飛んでいます.

だから3より低いタケノコはすべて出会って、3より大きい鍾乳石はすべてぶつかります.(上から下4の鍾乳石で下から2.5飛ぶホタルにぶつかった)

なぜなら、高さ6の洞窟では、高さ2の鍾乳石が高さ4(実質的に3.5)以上のホタルにぶつかるからだ.

つまりホタルが破壊する障害物の最小個数とこの最小値が現れる区間数を求める.

最初に思いついた方法は、タケノコと鍾乳石を別々に並べ、それぞれ並べて最初のホタルが衝突し始めた高さを計算することです.その後の区間はすべて衝突しているので、最初の区間からその区間までの個数を求めることでしか答えを求めることができません.この方法を累積(またはセグメント)

と呼ぶ.

石筍と鍾乳石の配列が別々に並んでいるので、並んでいる中間点でホタルが当たるかどうかのテストを行います.

一般的なバイナリ検索プロセスと同様にstart値とend値を変化させ、mid値を調整し、ホタルの最小衝突区間を見つければよい.

2. C++

区間木

#include <cstdio>

int n, h, answer, count;
int sum[500010];

int main() {
    scanf("%d %d", &n, &h);
    for (int i = 0 ; i < n ; i++) {
        int bar;
        scanf("%d", &bar);
        if (i & 1) {
            // 종유석
            sum[h - bar + 1]++;
        }
        else {
            // 석순
            sum[1]++;
            sum[bar + 1]--;
        }
    }
    answer = -1;
    for (int i = 1 ; i <= h ; i++) {
        sum[i] += sum[i - 1];
        if (answer == -1 || sum[i] < answer) {
            answer = sum[i];
            count = 1;
        }
        else if (sum[i] == answer) {
            count++;
        }
    }

    printf("%d %d", answer, count);
}

タイムアウト

#include <cstdio>

int n, h, answer, count;
int seok[200000], jong[200000];

// x구간으로 날아갈때 k번째 석순과 만나는지 
bool check_seok(int k, int x) {
    if (x <= seok[k]) return true;
    return false;
}

// x구간으로 날아갈때 k번째 종유석과 만나는지 
bool check_jong(int k, int x) {
    if (h - jong[k] + 1 <= x) return true;
    return false;
}

int fly(int x) {
    int res = 0;
    for (int i = 0 ; i < n ; i += 2) {
        // 석순과 만나는지
        if (check_seok(i, x)) res++; 
        // 종유석과 만나는지 
        if (check_jong(i, x)) res++;
    }
    return res;
}

int main() {
    scanf("%d %d", &n, &h);
    for (int i = 0 ; i < n ; i += 2) {
        scanf("%d", &seok[i]);
        scanf("%d", &jong[i]);
    }
    answer = -1;
    for (int i = 1 ; i <= h ; i++) {
        int crash = fly(i);
        if (answer == -1 || crash < answer) {
            answer = crash;
            count = 1;
        }
        else if (crash == answer) {
            count++;
        }
    }
    printf("%d %d", answer, count);
}