結果
問題 |
No.1211 円環はお断り
|
ユーザー |
|
提出日時 | 2025-02-24 02:24:58 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 92 ms / 2,000 ms |
コード長 | 1,867 bytes |
コンパイル時間 | 12,928 ms |
コンパイル使用メモリ | 246,876 KB |
実行使用メモリ | 10,124 KB |
最終ジャッジ日時 | 2025-02-24 02:25:16 |
合計ジャッジ時間 | 14,587 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 41 |
ソースコード
// 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]) } type dpItem struct{ count, next int } presum := make([]int, n+1) for i := 0; i < n; i++ { presum[i+1] = presum[i] + nums[i] } check := func(mid int) bool { // { // // 先求解链上的问题(剪枝) // count := 0 // left := 0 // for right := 0; right < n; right++ { // if presum[right+1]-presum[left] >= mid { // count++ // left = right + 1 // } // } // if count >= k { // return true // } // if count <= k-2 { // return false // } // } next := make([]int, n) right := 0 for left := 0; left < n; left++ { for right < n && presum[right]-presum[left] < mid { right++ } if presum[right]-presum[left] >= mid { next[left] = right } else { next[left] = -1 } } dp := make([]dpItem, n+1) dp[n] = dpItem{next: n} for i := n - 1; i >= 0; i-- { if next[i] == -1 { dp[i] = dpItem{next: i} } else { dp[i] = dp[next[i]] dp[i].count++ } } for i := 0; i < n; i++ { count := dp[i].count if count <= k-2 { break } end := dp[i].next if presum[n]-(presum[end]-presum[i]) >= mid { count++ } if count >= k { 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) }