🌺The Begin🌺点点关注，收藏不迷路🌺

题目描述

小蓝有n个装了水的瓶子，从左到右摆放，第i个瓶子里装有ai单位的水。水被循环染成k种颜色，即第i个瓶子和第i+k个瓶子的水颜色相同。

如果第i个瓶子和第j个瓶子中的水颜色相同且i<j，则可以将任意整数单位的水从第i个水瓶倒出，倒入第j个水瓶中。目标是经过任意次操作后，使所有瓶子中水的最小值最大化。

问题分析

关键点理解

1. 颜色分组：根据循环染色规则，我们可以将瓶子按颜色分组

   • 第i个瓶子的颜色为：(i-1) % k
   • 同颜色的瓶子构成一组，可以互相倒水（只能从编号小的往编号大的倒）

2. 操作限制：

   • 只能从编号小的瓶子往编号大的瓶子倒水
   • 倒水必须是整数单位
   • 可以倒任意次

3. 问题转化：

   • 对于每组同颜色的瓶子，水可以从左向右流动
   • 我们的目标是让所有瓶子的最小值尽可能大
   • 这相当于：将每组的水进行重新分配，使得每组的最小值最大化

解题思路

1. 按颜色分组：将瓶子按(i-1)%k的结果分成k组
2. 计算每组的最小可能最大值：
   • 对于一组瓶子，由于只能从左向右倒水，所以每个瓶子最终的水量不能超过它自身和它左边所有瓶子的平均值
   • 换句话说：对于位置j的瓶子，它最终的水量最多为前缀平均值：sum[0:j]/(j+1)
   • 整组瓶子最终的最小值，就是所有位置前缀平均值的最小值
3. 最终答案：取所有组中"最小可能最大值"的最小值

算法实现

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MIN(a, b) ((a) < (b) ? (a) : (b))

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    
    int *a = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    
    // 创建k个组，每个组存储对应颜色的瓶子
    int **groups = (int**)malloc(k * sizeof(int*));
    int *group_size = (int*)calloc(k, sizeof(int));
    
    // 计算每组的大小
    for (int i = 0; i < n; i++) {
        group_size[i % k]++;
    }
    
    // 分配每组内存
    for (int i = 0; i < k; i++) {
        groups[i] = (int*)malloc(group_size[i] * sizeof(int));
        group_size[i] = 0; // 重置为0，用于填充数据
    }
    
    // 填充每组数据
    for (int i = 0; i < n; i++) {
        int color = i % k;
        groups[color][group_size[color]++] = a[i];
    }
    
    int answer = INT_MAX;
    
    // 处理每组数据
    for (int color = 0; color < k; color++) {
        int size = group_size[color];
        long long sum = 0;
        int min_avg = INT_MAX;
        
        // 计算每组的前缀平均值
        for (int i = 0; i < size; i++) {
            sum += groups[color][i];
            int current_avg = sum / (i + 1); // 当前前缀平均值
            if (current_avg < min_avg) {
                min_avg = current_avg;
            }
        }
        
        // 取所有组的最小值
        if (min_avg < answer) {
            answer = min_avg;
        }
    }
    
    printf("%d\n", answer);
    
    // 释放内存
    for (int i = 0; i < k; i++) {
        free(groups[i]);
    }
    free(groups);
    free(group_size);
    free(a);
    
    return 0;
}

算法正确性证明

核心思想

对于每组同颜色的瓶子：

1. 由于只能从左向右倒水，每个瓶子的最终水量不会超过它之前所有瓶子的平均值
2. 要最大化最小值，最优策略是让所有瓶子的水量尽可能均匀
3. 实际能达到的最大最小值，就是所有前缀平均值的最小值

示例验证

输入：

7 3
8 5 5 2 2 3 4

分组情况：

• 颜色0（位置0,3,6）：8, 2, 4
• 颜色1（位置1,4）：5, 2
• 颜色2（位置2,5）：5, 3

计算每组的最小前缀平均值：

• 颜色0：
  • 第1个：8/1 = 8
  • 第2个：(8+2)/2 = 5
  • 第3个：(8+2+4)/3 = 14/3 ≈ 4.67
  • 最小值：4
• 颜色1：
  • 第1个：5/1 = 5
  • 第2个：(5+2)/2 = 3.5
  • 最小值：3
• 颜色2：
  • 第1个：5/1 = 5
  • 第2个：(5+3)/2 = 4
  • 最小值：4

取所有组的最小值：min(4, 3, 4) = 3，与样例输出一致。

复杂度分析

1. 时间复杂度：O(n)

   • 分组：O(n)
   • 计算每组前缀平均值：O(n)
   • 总时间复杂度：O(n)

2. 空间复杂度：O(n)

   • 存储分组数据：O(n)
   • 存储组信息：O(k)

注意事项

1. 整数除法：计算前缀平均值时使用整数除法，向下取整
2. 数据类型：使用long long存储和，防止溢出
3. 内存管理：需要动态分配内存，注意释放
4. 边界情况：
   • k=1时，所有瓶子同色
   • k=n时，每个瓶子颜色都不同，答案为数组最小值

测试用例

测试1

输入：

5 2
10 20 30 40 50

分组：

• 颜色0：10, 30, 50
• 颜色1：20, 40

计算：

• 颜色0：前缀平均值[10, 20, 30] -> 最小值10
• 颜色1：前缀平均值[20, 30] -> 最小值20
  答案：min(10, 20) = 10

测试2

输入：

4 4
1 2 3 4

每个瓶子颜色都不同，答案为最小值1

优化建议

对于特别大的n(100000)，上述算法完全可以在2秒内完成，因为时间复杂度为O(n)，空间复杂度也为O(n)，完全满足题目要求。

这个问题的关键在于理解同色瓶子之间的水流方向和如何最大化最小值，通过计算前缀平均值的最小值来得到最终答案。

🌺The End🌺点点关注，收藏不迷路🌺