P12167 [藍橋杯 2025 省 C/Python A] 倒水

題目描述

小藍有 $n$ 個裝了水的瓶子，從左到右擺放，第 $i$ 個瓶子里裝有 $a_i$ 單位的水。為了美觀，小藍將水循環染成了 $k$ 種顏色，也就是說，第 $i$ 個瓶子和第 $i+k$ 個瓶子里的水的顏色相同。

小藍發現有的瓶子里的水太少了，因此他規定如果第 $i$ 個瓶子和第 $j$ 個瓶子中的水顏色相同并且滿足 $i<j$，即可將任意整數單位的水從第 $i$ 個水瓶倒出，倒入第 $j$ 個水瓶中。小藍想知道任意次操作后所有瓶子中的水的最小值 min ? { a i } \min\{a_i\} min{ai?} 最大可以是多少？

輸入格式

輸入的第一行包含兩個正整數 $n,k$，用一個空格分隔。

第二行包含 $n$ 個正整數 $a_1,a_2,?,a_n$，相鄰整數之間使用一個空格分隔。

輸出格式

輸出一行包含一個整數表示答案。

輸入輸出樣例 #1

輸入 #1

7 3
8 5 5 2 2 3 4

輸出 #1

3

說明/提示

樣例說明

其中一種方案：

• $a_1$ 往 $a_4$ 倒入 $3$ 單位；
• $a_2$ 往 $a_5$ 倒入 $2$ 單位；
• $a_3$ 往 $a_6$ 倒入 $1$ 單位；
  最終每個瓶子里的水：$5,3,4,5,4,4,4$，最小值為 $3$。

評測用例規模與約定

• 對于 $40\%$ 的評測用例，$1\le n,a_i\le 100$；
• 對于所有評測用例，$1\le n,a_i\le 100000$，$1\le k\le n$。

P12167 [藍橋杯 2025 省 C/Python A] 倒水

【思路分析】

求最小值最大，一般考慮二分。而這個題可以按照不同顏色進行分組，判斷能否將所有分組的最小值達到某數x，而x通過二分進行查找

import java.util.*;
import java.io.*;
public class Main {static int[] a = new int[100005];static int n, k;// 檢查是否可以使每個顏色組的瓶子水量最小值達到 xstatic boolean check(int x) {// 遍歷每個顏色組for (int i = 1; i <= k; i++) {// j 用于遍歷當前顏色組內的瓶子int j = i;// d 用于記錄當前顏色組內水量的盈余情況long d = 0;// 遍歷當前顏色組內的所有瓶子while (j <= n) {// 如果當前瓶子的水量大于等于 xif (a[j] >= x) {// 計算當前瓶子的水量盈余，并累加到 d 中d += a[j] - x;} else {// 如果當前瓶子的水量小于 x，計算需要補充的水量，并從 d 中扣除d -= (x - a[j]);}// 如果盈余水量小于 0，說明無法使當前顏色組內所有瓶子的水量都達到 xif (d < 0) {return false;}// 移動到下一個同顏色組的瓶子j += k;}}// 如果所有顏色組都能滿足條件，則返回 truereturn true;}public static void main(String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] row1 = br.readLine().split(" ");n = Integer.parseInt(row1[0]);k = Integer.parseInt(row1[1]);String[] data = br.readLine().split(" ");for (int i = 1; i <= n; i++) {a[i] = Integer.parseInt(data[i - 1]);}int l = 1;int r = 100000;while (l <= r) {int mid = (l + r) >> 1;if (check(mid)) {l = mid + 1;} else {r = mid - 1;}}System.out.println(l - 1);br.close();}
}