创建免费网站需要什么条件,移动端网站设计制作,红酒企业网站建设,河间网站建设P12167 [蓝桥杯 2025 省 C/Python A] 倒水
题目描述
小蓝有 n n n 个装了水的瓶子#xff0c;从左到右摆放#xff0c;第 i i i 个瓶子里装有 a i a_i ai 单位的水。为了美观#xff0c;小蓝将水循环染成了 k k k 种颜色#xff0c;也就是说#xff0c;第 i i i …P12167 [蓝桥杯 2025 省 C/Python A] 倒水
题目描述
小蓝有 n n n 个装了水的瓶子从左到右摆放第 i i i 个瓶子里装有 a i a_i ai 单位的水。为了美观小蓝将水循环染成了 k k k 种颜色也就是说第 i i i 个瓶子和第 i k i k ik 个瓶子里的水的颜色相同。
小蓝发现有的瓶子里的水太少了因此他规定如果第 i i i 个瓶子和第 j j j 个瓶子中的水颜色相同并且满足 i j i j ij即可将任意整数单位的水从第 i i i 个水瓶倒出倒入第 j j j 个水瓶中。小蓝想知道任意次操作后所有瓶子中的水的最小值 min { a i } \min\{a_i\} min{ai} 最大可以是多少
输入格式
输入的第一行包含两个正整数 n , k n, k n,k用一个空格分隔。
第二行包含 n n n 个正整数 a 1 , a 2 , ⋯ , a n a_1, a_2, \cdots, a_n a1,a2,⋯,an相邻整数之间使用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。
输入输出样例 #1
输入 #1
7 3
8 5 5 2 2 3 4输出 #1
3说明/提示
样例说明
其中一种方案 a 1 a_1 a1 往 a 4 a_4 a4 倒入 3 3 3 单位 a 2 a_2 a2 往 a 5 a_5 a5 倒入 2 2 2 单位 a 3 a_3 a3 往 a 6 a_6 a6 倒入 1 1 1 单位 最终每个瓶子里的水 5 , 3 , 4 , 5 , 4 , 4 , 4 5, 3, 4, 5, 4, 4, 4 5,3,4,5,4,4,4最小值为 3 3 3。
评测用例规模与约定
对于 40 % 40\% 40% 的评测用例 1 ≤ n , a i ≤ 100 1 \leq n, a_i \leq 100 1≤n,ai≤100对于所有评测用例 1 ≤ n , a i ≤ 100000 1 \leq n, a_i \leq 100000 1≤n,ai≤100000 1 ≤ k ≤ n 1 \leq k \leq n 1≤k≤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();}
}
