2021牛客寒假训练营5D石子游戏（差分）

2021牛客寒假训练营5D石子游戏（差分）

这个题无解的情况后台数据高达80%，一开始过了10%以为写假了​​​光巨​​​昨晚讲的太好了，今天上线写一下题目大意： 给你n堆石子和一个区间k，每次对一个长度一定为k的区间里的所有数字加一，问最少操作次数使得所有的数都相等思路： 对于一个区间的加减操作，我们很容易想到差分数组 我们直接考虑最终状态

最终状态的差分数组W 0 0 0 0 0 0

那么考虑初始状态

w1 w2 w3 w4 w5 (可能为负)

我们差分数组操作的时候，如果对[x,y]区间加一的话 只需要b[x]++ b[y+1]– 回到差分数组中 如果在pos1这个位置一个w小于0 那么我们把它变为0 对应的pos1+k的位置要+w 相当于对[pos1,pos1+k-1]这个区间加了w（注意边界）

我们第一次扫数组的时候要倒着扫 （好像也可以先正着扫） 我们倒着扫一边之后还有一个细节没有考虑到 因为我们是从n这个位置开始的 但是在差分数组中n+1的这个位置也是可以操作的 所以数组中就会存在一些特殊点这些特殊点有一个共同的性质： 1.就是如果我在差分数组中操作这个点，他一定会影响到b[n+1]这个位置的值的加减的权重2. 点集在模k的余数相等 所以我们最后把这些特殊点单独拿出来重新扫一边最后无解记得输出-1

Code：

ll n,k,a[maxn],b[maxn];int main() { int toto = read(); while(toto--) { n=read(),k=read(); rep(i,1,n) a[i] = read(); rep(i,1,n) b[i] = a[i] - a[i-1]; ll ans=0; for(int i=n ; i>=1 ; i--) { if(i-k==0) break; if(b[i]<=0) continue; ll w=b[i]; ans+=w; b[i]=0; b[i-k]+=w; } int pos = n - k +1; // last pos in sequence int yu = pos%k; for(int i=1 ; i<=n ; i++) { if(b[i]>0) continue; if(i%k==yu) { int w = abs(b[i]); b[i]=0; ans+=w; b[i+k]-=w; } } rep(i,2,n) if(b[i]!=0) ans =-1; out(ans); puts(""); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。