[HNOI2009]通往城堡之路

脑洞 贪心

题面

给一个长度为$n$的序列$\{a\}$。现可改变第$2～n-1$个数的权值，使序列个数相差不超过$d$。最小化权值改变大小之和。

• $n\leq5000$

解析

留坑待填

这题很奇妙咦
无解显然是$abs(a[1]-a[n])>(n-1)*d$。

注意到，最终序列$a'$一定符合一个限制：$a'_i>=a[1]-(i-1)*d$
于是可以先把序列中所有值（除第一个）改为最小值，然后看怎么提高。

给一段区间同时升高$h$米。
为了方便，假设区间内$a_i$只有两种情况：$a_i+h\leq b_i\ or\ a_i\geq 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}+d\geq 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\n",ans);
    }
  return 0;
}