题目描述

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

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

输入格式

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

第二行包含 n 个正整数 a1​,a2​,⋯,an​，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

输入输出样例

输入 #1复制

7 3
8 5 5 2 2 3 4

输出 #1复制

3

说明/提示

样例说明

其中一种方案：

• a1​ 往 a4​ 倒入 3 单位；
• a2​ 往 a5​ 倒入 2 单位；
• a3​ 往 a6​ 倒入 1 单位； 最终每个瓶子里的水：5,3,4,5,4,4,4，最小值为 3。

评测用例规模与约定

• 对于 40% 的评测用例，1≤n,ai​≤100；
• 对于所有评测用例，1≤n,ai​≤100000，1≤k≤n。

#include <bits/stdc++.h>
using namespace std;
const int N =100001;
#define int long long
struct Node
{
int sum=0;int cnt=0;
}s[N];
signed main()
{
    int a[N];
    int n,k;
    int ans=100001;
    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);
/*为什么要取最小值？首先题目要求是最小值的最大值，必须有一个取最大和取最小吧。
1.取平均值本身就是为了更大 那再取最小值就是在同颜色里取最小值最大的情况 那凭什么前面几个就能代表后面的所有？如果+1的前缀和平均值变大的话 那也没用 因为求的是最大值的最小 所以大的不考虑 小的就更新 但过程还是遍历了同种颜色的所有元素 
2.取最小。
*/
        }
    cout<<ans<<endl;
    return 0;
}