有的人的题解都是差分,我的方法是贪心+模拟,在方法普适性上不及差分,但这题确实可以当做思维题来写.

首先发现前k个中若存在a[i]<a[i+1] (1<=i<=k-1),那我们没有办法使n堆石子数量相等

然后我们可以贪心地从前往后用i遍历每堆石子,观察a[i],a[i+1]的关系,
1.若a[i]<a[i+1],前i堆必须都增加成a[i+1]个石子.
2.若a[i]==a[i+1],那么继续遍历
3.若a[i]>a[i+1],则a[i+1]~a[i+k] 都要增加成a[i]个石子

遍历过程我们始终贪心地立刻使a[i]==a[i+1],
因为你同时增加相邻k堆的数量,若第i堆和第i+1堆同时在这k堆里,那他们的相对关系不变,无法得到a[i]==a[i+1],也就无法使n堆石子数量相等,
只有增加① a[i-k+1]a[i]或② a[i+1]a[i+k],才能改变a[i]和a[i+1]之间的相对关系(显然a[i]小使增加①的数量),所以这个贪心算法的正确性证毕.

下面列出关于贪心过程中判断无法使n堆石子数量相等的条件,证明留给读者
1.a[i]<a[i+1] && i%k!=0 2.a[i]>a[i+1] && i>=n-k+1

最后讲完,发现这个贪心和用差分本质上相同,因为博主知识不扎实故只想出了复杂的较高(因为a[i]>a[i+1]时要模拟改k个值)的贪心模拟法
不过,本方法对理解差分有一定帮助.

代码:

#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<cmath>
#define rep(i,a,b) for(ll i=a;i<=b;++i)
#define per(i,a,b) for(ll i=a;i>=b;--i)
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
const int maxn=1e5+10,inf=0x3f3f3f3f;

ll a[maxn];

int main()
{
    int t ;
    cin>>t;
    while(t--){
        memset(a,0,sizeof(a));
        int n,k;cin>>n>>k;
        rep(i,1,n) cin>>a[i];

        ll ans=0;
        if(k==1){    //特判不是很必要,归并到下面的模拟也行
            ll ma=*max_element(a+1,a+1+n);        
            rep(i,1,n){
                ans+=ma-a[i];
            }
            cout<<ans<<endl;
            continue;
        }

        bool flag=1;
        rep(i,1,n-1){
            if(a[i]<a[i+1]){    //这里不必模拟修改a[i-k+1]~a[i],因为i向前不回头,我们接下来"认为"前i+1堆都是a[i+1]个石子
                if(i%k!=0) {flag=0;break;}
                else ans+=(a[i+1]-a[i])*(i/k);
            }
            else if(a[i]>a[i+1]) {
                if(i>=n-k+1)    {flag=0;break;}
                else {
                    ll sub=(a[i]-a[i+1]);
                    ans+=sub;
                    rep(j,1,k)
                        a[i+j]+=sub;
                }
            }
        }
        cout<<(flag?ans:-1)<<endl;
    }
    return 0;
}