結果

問題 No.1211 円環はお断り
ユーザー 草苺奶昔
提出日時 2025-02-24 01:36:27
言語 Go
(1.23.4)
結果
WA  
実行時間 -
コード長 1,306 bytes
コンパイル時間 12,445 ms
コンパイル使用メモリ 250,832 KB
実行使用メモリ 10,136 KB
最終ジャッジ日時 2025-02-24 01:36:43
合計ジャッジ時間 14,902 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 36 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

// No.1211 円環はお断り(圆环)
// https://yukicoder.me/problems/no/1211
// !给定一个环形数组,分成k个非空连续子数组,使得这k个子数组的和的最小值最大,求出这个最大的最小值.

package main

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

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, k int
	fmt.Fscan(in, &n, &k)
	nums := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &nums[i])
	}

	presum := make([]int, n+1)
	for i := 0; i < n; i++ {
		presum[i+1] = presum[i] + nums[i]
	}

	check := func(mid int) bool {
		count := make([]int, n)
		leftMost := make([]int, n)
		for i := 0; i < n; i++ {
			count[i] = 1
			leftMost[i] = i
		}
		left := -1
		for right := 0; right < n; right++ {
			for left+1 < right && presum[right]-presum[left+1] >= mid {
				left++
			}
			if left >= 0 {
				count[right] = count[left] + 1
				leftMost[right] = leftMost[left]
				if count[right] == k {
					// 首尾
					if presum[n]-(presum[right]-presum[leftMost[right]]) >= mid {
						return true
					}
				}
			}
		}
		return false
	}

	left, right := 1, presum[n]/k+1
	for left <= right {
		mid := (left + right) / 2
		if check(mid) {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	fmt.Fprintln(out, right)
}
0