https://www.zybuluo.com/ysner/note/1251235
题面
给一个长度为(n)的序列({a})。现可改变第(2～n-1)个数的权值，使序列个数相差不超过(d)。最小化权值改变大小之和。
- (nleq5000)
解析
留坑待填
这题很奇妙咦
无解显然是(abs(a[1]-a[n])>(n-1)*d)。
注意到，最终序列(a')一定符合一个限制：(a'_i>=a[1]-(i-1)*d)
于是可以先把序列中所有值（除第一个）改为最小值，然后看怎么提高。
给一段区间同时升高(h)米。
为了方便，假设区间内(a_i)只有两种情况：(a_i+hleq b_i or a_igeq b_i)。
( 其实这个情况很好保证，只要扫一遍取(h=min{b_i-a_i}))
如果第一种情况有(r)个，第二种情况有(s)个，则(ans-=(r-s)*h)。
于是我们的目标就是使(r-s)和(h)同号（(h)可以为负）。
应用一下差分思想，发现可以用两个后缀区间表示一段区间。
于是就不用枚举右端点了。
然后可以发现，其实只要枚举左端点，在区间内取(h=min{b_i-a_i})，然后给所有区间同时升高(h)，以此类推，总能使答案更优。
并且(b[n])只能升到(a[n])，不能变得更大。
则答案最优时，(a[n]=b[n])。
当然也要注意修改的合法性，如(a_{l-1}+dgeq a_l)。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int mod=1e9+7,N=5050;
ll n,d,a[N],b[N],ans;
il ll gi()
{
re ll x=0,t=1;
re char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
int main()
{
re int T=gi();
while(T--)
{
n=gi();d=gi();ans=0;
fp(i,1,n) b[i]=a[i]=gi();
if(abs(a[1]-a[n])>(n-1)*d) {puts("impossible");continue;}
fp(i,2,n) b[i]=b[i-1]-d;
while(a[n]^b[n])
{
re ll s=0,mn=1e18,mx=-1e18,pos,add=1e18;
fq(i,n,2)
{
if(b[i]<a[i]) ++s,mn=min(mn,a[i]-b[i]);
else --s;
if(s>mx&&b[i-1]+d!=b[i]) mx=s,pos=i,add=mn;
}
add=min(add,b[pos-1]+d-b[pos]);
fp(i,pos,n) b[i]+=add;
}
fp(i,1,n) ans+=abs(a[i]-b[i]);
printf("%lld
",ans);
}
return 0;
}