P12167 [蓝桥杯 2025 省 C/Python A] 倒水

题目描述

小蓝有 $n$ 个装了水的瓶子，从左到右摆放，第 $i$ 个瓶子里装有 $a_i$ 单位的水。为了美观，小蓝将水循环染成了 $k$ 种颜色，也就是说，第 $i$ 个瓶子和第 $i+k$ 个瓶子里的水的颜色相同。

小蓝发现有的瓶子里的水太少了，因此他规定如果第 $i$ 个瓶子和第 $j$ 个瓶子中的水颜色相同并且满足 $i<j$，即可将任意整数单位的水从第 $i$ 个水瓶倒出，倒入第 $j$ 个水瓶中。小蓝想知道任意次操作后所有瓶子中的水的最小值 min⁡{ai}\min\{a_i\}min{ai​} 最大可以是多少？

输入格式

输入的第一行包含两个正整数 $n,k$，用一个空格分隔。

第二行包含 $n$ 个正整数 $a_1,a_2,\cdots ,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$。

C++实现

//luogu P12167
#include <bits/stdc++.h>
using namespace std;
const int M=100010;
struct Node { //用于表示每种颜色的情况
    long long sum=0,cnt=0; //sum前缀和 cnt数量
} s[M];
long long n,k;
long long a[M],ans=1e9;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    for(int i=1; i<=n; i++) {
        cin>>a[i];
        s[i%k].sum+=a[i];
        s[i%k].cnt++;
        ans=min(s[i%k].sum/s[i%k].cnt,ans);
    }
    cout<<ans;
    return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容