%k分类

假设k=3，第1个长度为k的区间和为$s_1=a_1+a_2+a_{3}s\_1=a\_1+a\_2+a\_3$（数组下标从1开始），第二个长度为k的区间和为$s_2=a_2+a_3+a_{4}s\_2=a\_2+a\_3+a\_4$。

题目要求所有长度为k的区间和相等，也就是$s_1=s_{2}s\_1=s\_2$，因此$a_1=a_{4}a\_1=a\_4$，逐步迭代下去，由于每个区间和都相等，我们应该有：

因此可以对数组按照%k进行分类，%k相同的做为一组，并且要保证这个组内的所有数都相。

对于某个组$pp$，由于每次的操作是+1，数字只能增加不能减少，所以需要找到组内的最大值$mxmx$，并将组内所有的数变成$mxmx$，所需要的时间是$t=mx\times p\mathrm{.}size()-sum(p)t=mx\backslash times\; p.size()\; -\; sum(p)$.

计算出所有组所需要的时间$cntcnt$，如果$cnt>xcnt\; >\; x$，就输出-1。

找到最大值

否则x -= cnt，为了拿到最大值，并且要保证每个组内的数都相等，可以遍历每个组，并将x均分给组内的每一个数，找到最后的最大值即可。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int a[N];

int n, k, x;

void solve(){
    cin >> n >> k >> x;
    for(int i = 1; i <= n; ++ i)
        cin >> a[i];
    unordered_map<int, vector<int> > mhash; // 存储i % k相同的数
    for(int i = 1; i <= n; ++ i)
        mhash[i % k].push_back(a[i]);
    int cnt = 0;
    for(auto& [k, v] : mhash){
        sort(v.begin(), v.end()); // 排序便于找最大值
        int mx = v.back(); // 最大值
        for(int& num : v){
            cnt += abs(num - mx); // num变为mx所需要的最大值
            num = mx; // 将num变为mx
        }
    }
    if(cnt > x) {cout << -1 << endl; return;}
    x -= cnt;
    int res = *max_element(a + 1, a + 1 + n); // 找到原来数组内的最大值
    for(auto& [k, v] : mhash){
        res = max(res, v.back() + x / (int)v.size());
    }
    cout << res << endl;
}

int main(){
    int T;
    cin >> T;
    while(T -- ){
        solve();
    }
}