[BOJ]1756号:焼きピザ(Go,Golang)

9161 ワード
go algorithm baekjoon テキストリンク
質問リンク:白駿1756号です。

[質問へのアクセス]


dとnをすべて検索するとタイムアウトが発生するので最適化が必要です.
nと生地を固定する個数dを二分探索により実現した.
こちらを探索するためには、ソートが必要で、オーブンの特徴を利用すればOKです.
幅5のオーブンの下に幅6のオーブンがあり、6のピザも絶対入らない.つまり、自分の上のオーブンより大きくても意味がありません.
そのため、オーブンの幅は5 5 5 4 3 2と言えます.△オーブンを上から見下ろすとき、見えるように思えば簡単です.
このようにオーブンの幅を並べて二分探索を行い、ピザの幅がオーブンの幅より小さい場合、ピザの幅がオーブンの幅に等しいか等しい場合は、一番下のオーブンに入れることができます.
次のピザを置くとき、endは前に置いたオーブンにindex-1を設置し、既存のピザの下に置くことはできません.
0の場合、このピザはオーブンに入れられないので、0を出力できます.

[ソースコード]

package main

import (
	"bufio"
	"fmt"
	"os"
)

var (
	r    = bufio.NewReader(os.Stdin)
	w    = bufio.NewWriter(os.Stdout)
	d, n int
)

func main() {
	defer w.Flush()
	fmt.Fscan(r, &d, &n)
	oven := make([]int, d+1)
	pizza := make([]int, n+1)
	tmp := 0
	for i := 1; i <= d; i++ {
		fmt.Fscan(r, &oven[i])
		if i == 1 {
			tmp = oven[i]
		} else {
			if tmp < oven[i] {
				oven[i] = tmp
			} else {
				tmp = oven[i]
			}
		}
	}

	for i := 1; i <= n; i++ {
		fmt.Fscan(r, &pizza[i])
	}
	down := d
	check := true
	for i := 1; i <= n; i++ {
		start, end := 1, down
		pos := 0
		for start <= end {
			mid := (start + end) / 2
			if oven[mid] >= pizza[i] {
				start = mid + 1
				pos = mid
			} else {
				end = mid - 1
			}
		}
		if pos == 0 {
			check = false
			continue
		} else {
			down = pos - 1
		}
	}
	if check {
		fmt.Fprintln(w, down+1)
	} else {
		fmt.Fprintln(w, 0)
	}

}
5分未満でRXJSオブザーバブルを明らかにすること
ページ分割と限界突破