ほたる

ソース:白駿#2020
タイムアウトメモリ制限1秒128 MB

質問する

1匹のホタルが障害物(タケノコと鍾乳石)だらけの洞窟に入った.穴の長さはNメートル,高さはHメートルである.(Nは偶数)最初の障害物は常にタケノコであり,次いで鍾乳石とタケノコが交互に現れる.
下の図は長さ14メートル、高さ5メートルの洞窟です.(例図)

この犬の糞虫は障害を避けない.自分が通る区間を確定し、直線に沿って走り、出会ったすべての障害物を破壊する.
上図では、ホタルが4番目の区間に飛んだ場合、破壊する必要がある障害物の総数は8個である.(4段目は長さ3のタケノコと長さ4のタケノコの中間部分を指す)

しかし、第1段または第5段に飛ぶと、犬糞虫は7つの障害物を破壊するだけだ.
洞窟の大きさと高さ、すべての障害物の大きさ.このとき,ホタルが破壊すべき障害物の最大値と,これらの障害物の総区間数を求めるプログラムを作成する.

入力

第1行はNとHを与える.Nは常に偶数である.(2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000)
次のN行は障害物の大きさを順次与える.障害物の大きさはHより小さい正数である.

しゅつりょく

1行目では、ホタルが破壊する障害物の最大値と対応する区間数をスペースで区切ります.

I/O例

入力例1

6 7
1
5
3
3
5
1

サンプル出力1

2 3

入力例2

14 5
1
3
4
2
2
4
3
4
3
3
3
2
3
3

サンプル出力2

7 2

に答える

思考と解答説明

上限で解決しました.

共通

は、まずタケノコ(ダニ)と鍾乳石(tit)の2つのリストでそれぞれ情報を受信する.

はバイナリ探索をソートする.(この部分が大事!!)

バイナリナビゲーションは、整列した状態で使用する必要があります.

のアイデアを思いついたときにソートしたい場合は、バイナリで検索する問題かどうかを知ることができます.

鍾乳石(tit)に直接値を入力するのではなく、高さから減算するのは起点を0にして計算するためです.

席でtempに会う前のインデックスを返します.(r1)
したがって、n/2から減算された値を加算する必要があります.

鍾乳石時にh-tempに会う前のインデックスを返します.(r2)

の場合、h-tempは最初は鍾乳石のない部分に相当するので、直接戻ります.

r 1およびr 2の和をそのときの最小値と比較し、同じであればresult += 1、より小さい場合は最小値を更新する.

python code (upper bound)

# 백준 3020번 개똥벌레
from sys import stdin
input = stdin.readline
n, h = map(int, input().split())
mite, tite = [], [] # 석순, 종유석

def binarySearch_UpperBound(start, end, arr, target):
    while start < end:
        mid = (start+end)//2
        if arr[mid] <= target:
            start = mid + 1
        else:
            end = mid
    return start

for i in range(n//2):   # 입력 횟수 절반으로 줄임
    mite.append(int(input())) # 석순
    tite.append(h-int(input())) # 종유석    # [6, 4, 2]

mite.sort()   # 석순 오름차순 정렬
tite.sort()   # 종유석 오름차순 정렬

min_num, result = n, 0

for i in range(1, h+1):
    r1 = n//2 - binarySearch_UpperBound(0, n//2, mite, i-1)     # 닿은 면 체크
    r2 = binarySearch_UpperBound(0, n//2, tite, i-1)   # 닿지 않은 면 체크
    total = r1 + r2 # (총 닿은 면 개수)
    if min_num == total:
        result += 1
    elif min_num > total:
        min_num = total
        result = 1

print(min_num, result)