题解 P3202 【[HNOI2009]通往城堡之路】
wuzhoupei
2017-10-26 21:17:23
太难了；
首先，它标了个Tarjan的标签；
然后，应该是有人用什么仙人掌+DP做的吧；
然而还是用的贪心；
根本不会；
****
就是把所有的==都先设为最差值==；
然后一点点的往上调；
然后就是贪心；
> 定义 ：
low : 从n到现在i b[i]<=a[i] 的个数；
up : 从n到现在i b[i]>a[i] 的个数；
我们找一个 ==low-up 最大的后缀==；
先上调；
调的距离是 min ( a[i]-b[i] ) |a[i]>b[i];
因为这样我们 up 增加的值可以用 low 增加的值来==抵消==；
而且会有一部分 low 的值会使 ans 减小；
所以最优；
但是上调距离==有边界==， 即前一个 b[i-1]+d < b[i];
所以 b[i] 上调的最大距离要和 b[i-1]+d-b[i] 取 min；
****
```cpp
#include "iostream"
#include "stdio.h"
#include "algorithm"
#define II int
#define LO long long
#define R register
#define I 123456
using namespace std;
II t,n;
LO d;
LO a[I], b[I];
LO gg(R LO x) { return x<0 ? -x : x ; }
LO smaler(R LO a,R LO b) { return a<b ? a : b ; }
int main()
{
scanf("%d",&t);
while (t--) {
scanf("%d%lld",&n,&d);
for(R II i=1;i<=n;i++) scanf("%lld",&a[i]);
if(gg(a[n]-a[1])>d*(n-1)) {
printf("impossible\n");
continue ;
}
b[1]=a[1];
for(R II i=2;i<=n;i++) b[i]=b[i-1]-d;
while (b[n]!=a[n]) {
R LO low=0,up=0,wei,oo=-1e18,op=1e18, ko=0;
for(R II i=n;i>1;i--)
{
a[i]>b[i] ? low++ : up++ ;
if(a[i]>b[i]) {
op=smaler(op,a[i]-b[i]);
}
if(low-up>=oo && b[i-1]+d!=b[i]) {
oo=low-up;
wei=i;
ko=op;
}
}
ko=smaler(ko,b[wei-1]+d-b[wei]);
for(R II i=wei;i<=n;i++) b[i]+=ko;
}
R LO ans=0;
for(R II i=1;i<=n;i++) ans+=gg(a[i]-b[i]);
printf("%lld\n",ans);
}
exit(0);
}
```
****