石子游戏

前不久刚做了一题差分的题，看到这题联想起来了
AcWing 100. 增减序列

做法：差分

思路：

• 每次操作把连续相邻的k个石子堆中的每堆石子数目加一,联想到差分
  设左右端点分别为l,r时，每次操作b[l]+=c;b[r+1]-=c;
  根据这一特性，模拟即可
  最后检查一遍可行性

代码

// Problem: 石子游戏
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/9985/D
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
#define debug(a) cout<<#a<<":"<<a<<"\n"
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=100010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

ll a[N],b[N];

void solve(){
    int n,k;cin>>n>>k;
    rep(i,1,n){
        cin>>a[i];
        b[i]=a[i]-a[i-1];  //构造差分数组
    }
    ll ans=0;

    // rep(i,2,n) cout<<b[i]<<" \n"[i==n];

    rep(i,2,n-k){
        if(b[i]<0){
            ll t=-b[i];
            b[i]+=t;
            ans+=t;
            b[k+i]-=t;
        }
    }
    // debug(ans);
    // rep(i,2,n) cout<<b[i]<<" \n"[i==n];
    // for(int i=1;i<=n;i++){
        // a[i]=a[i-1]+b[i];
        // cout<<a[i]<<" \n"[i==n];
    // }
    per(i,n,k+1){
        if(b[i]>0){
            ll t=b[i];
            b[i]-=t;
            ans+=t;
            b[i-k]+=t;
        }
    }
    // debug(ans);
    // rep(i,2,n) cout<<b[i]<<" \n"[i==n];
    // for(int i=1;i<=n;i++){
        // a[i]=a[i-1]+b[i];
        // cout<<a[i]<<" \n"[i==n];
    // }
    if(b[n-k+1]<0) ans-=b[n-k+1],b[n-k+1]=0;
    rep(i,2,n){
        if(b[i]){
            cout<<"-1\n";
            return;
        }
    }
    cout<<ans<<"\n";
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int t;cin>>t;while(t--)
    solve();
    return 0;
}