同様の標準問題https://www.acmicpc.net/problem/2805
問題で要求されたのは魏伯俊問題と同じだ.トッポッキから木になっただけです.

に近づく

初めて

まず問題を見てから、バイナリ検索で最大の長さを見つけたいです.だから、トッポッキの長さの配列を探索し、中間点を探す方法で表現しますが、よく考えてみると、配列にない数字が答えかもしれません.だから、私はこの接近が間違っていることに気づいた.

2回目

バイナリ検索により,最大最小値を探し出し,両者の平均値を中間としてtargetと同じ方法で実現するかどうかを検索する.このため,複雑度O(N),バイナリ探索O(logn)の残留餅長の和を求める関数をそれぞれ実現し,ある程度は悪くない.

def sum_left(array, length):
	result = 0
	for i in array:
		left = i - length
		if left <= 0:
			continue
		result += left
	return result

def binary_search(array, target, min, max):
	while min <= max:
		mid = (min + max) // 2
		tmp = sum_left(array, mid)
		if tmp == target:
			return mid
		elif tmp > target:
			max = mid - 1
		else:
			min = mid + 1
	return -1

しかし、このコードにも問題があります.二日間悩んで、時間さえあれば解けると思ったが、もう時間がかからないので、答えを見てから勉強したい.

解説

プロセス全体と私が試した方法はあまり違いません.しかし、上記のコードや説明とは異なる部分が条件部分です.上記のコードでは,tmpがtargetになった場合と異なる場合を別々に処理すべきであるが,この部分ではずっといくつかの問題が解決されていない.しかし解説からは単純にtmpimport sys def solution(): n , m = list(map(int, input().split())) array = list(map(int, sys.stdin.readline().rstrip().split())) start = 0 end = max(array) result = 0 while start <= end: mid = (start + end) // 2 total = 0 for i in array: if i > mid: total += i - mid if total < m: # 떡이 부족한 경우 end = mid - 1 else: result = mid start = mid + 1 print(result) solution()ちなみに、このようなソリューションと呼ばれる方法で関数を作成して実行すると、関数を使用せずに直接コードを記述するよりも処理速度が速くなります.これは、関数で実装されると変数がローカル変数として宣言され、関数実装がない場合はグローバル変数として宣言されるため、いくつかの明らかな速度差が生じるためです.(出典:https://stackoverflow.com/questions/11241523/why-does-python-code-run-faster-in-a-function)