P8175
_SeeleVollerei_
·
·
题解
为了防止下一个看到这道冷门题然后不会做且不知道如何是好的人，为这题写一篇题解。
我们不妨把 Wilco 抽象成时间，意思就是每次在 i 拿糖果需要满足当前时间 \le 2\times(i-1)。
显然拿糖果的顺序一定是从左往右的，因为如果先拿右边再拿左边可行，那么反过来一定也可行。相当于整条路径有一条向右的轮廓。意味着我们要走到 i 首先需要 i-1 的时间，那么剩下的 i-1 的时间就是为了糖果花费的额外时间。我们考虑去维护这个额外时间。
一个难点在于我们不知道每个糖果拿完后是走到左边的游乐场还是右边的游乐场。不妨按照游乐场分为若干段，对于每一段，我们发现可以不花任何额外代价地拿走一个糖果，也就是从游乐场 l 走到糖果店 i，然后再走到游乐场 r。
以这个白嫖的糖果为分界点，那么这个糖果左边的所有糖果都会回收到 l，这个右边的所有糖果都会回收到 r。也就是说我们只需要确定这个白嫖的糖果在哪，就能确定每个糖果的贡献。
考虑计算每个糖果的贡献。
对于 $i$，显然一次糖果的贡献就是 $2\times(i-l)$，而且是只要当前的额外贡献（不考虑这个糖果的贡献）也就是 $now\le i-1$ 就能拿一次糖果。
比较复杂的是右边 $j$ 和 $k$ 的情况。我们沿虚线切开，发现对于 $j$ 左边的路径去掉，对于 $j$ 多的贡献是 $2\times(r-j)$。只不过这个是在拿糖果之前贡献的，也就是要求 $now+2\times(r-j)\le j-1$ 才能拿到这个糖果。而看上去我们是预支了一段 $r-mid$ 上的 $r-j$，但是实际上下面还有一段 $r-j$，所以 $j$ 的贡献在后面对于 $k$ 来讲依然是 $2\times (r-j)$。
归纳一下就是无论哪边一个糖果的贡献都是 $2\times \min(i-l,r-i)$。
那么对于中间的糖果，我们直接取 $\min(i-l,r-i)$ 最大的糖果即可。因为对于任意最优的方案，我们把白嫖的糖果调整为当前糖果一定不劣。
那么拿个堆维护一下前面所有的贡献，然后跑一个带反悔的贪心即可。不过这个反悔贪心比较直观。
```cpp
#include<cstdio>
#include<queue>
using namespace std;
typedef long long LL;
const int N=5e5+5;
const int INF=0x3f3f3f3f;
int n,a[N];
int pre[N],suf[N];
int dis[N];
inline int Read(){
char ch;
int f=1;
while((ch=getchar())<'0'||ch>'9')
if(ch=='-') f=-1;
int x=ch^48;
while((ch=getchar())>='0'&&ch<='9')
x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
inline void print(LL x){
if(x>=10) print(x/10);
putchar(x%10+48);
return ;
}
inline void Print(LL x,char ch='\n'){
if(x<0){
putchar('-');
print(-x);
}
else print(x);
putchar(ch);
return ;
}
inline int Max(int x,int y){
return x>y?x:y;
}
inline int Min(int x,int y){
return x<y?x:y;
}
inline void Cmax(int&x,int y){
if(y>x) x=y;
return ;
}
inline void Cmin(int&x,int y){
if(y<x) x=y;
return ;
}
inline void Init(){
n=Read();
for(int i=1;i<=n;i++)
a[i]=Read();
a[0]=a[n+1]=-1;
pre[0]=0;
for(int i=1;i<=n;i++)
if(a[i]==-1) pre[i]=i;
else pre[i]=pre[i-1];
suf[n+1]=n+1;
for(int i=n;i;i--)
if(a[i]==-1) suf[i]=i;
else suf[i]=suf[i+1];
for(int i=1;i<=n;i++){
dis[i]=INF;
if(pre[i]) Cmin(dis[i],i-pre[i]);
if(suf[i]!=n+1) Cmin(dis[i],suf[i]-i);
}
return ;
}
priority_queue<int>que;
int mx;
LL ans;
LL now;
inline void Solve(){
for(int p=0,q;p<=n;p=q){
q=p+1;
while(a[q]!=-1) q++;
int mid=0;
for(int i=p+1;i<=q-1;i++){
if(a[i]==0) continue ;
if(dis[i]>dis[mid]) mid=i;
}
if(!mid) continue ;
mx++;
a[mid]--;
for(int i=p+1;i<=mid;i++){
if(!a[i]) continue ;
for(int j=1;j<=a[i];j++){
if(now<=i-1&&now+2*dis[i]<=mid-1){
mx++;
now+=2*dis[i];
que.push(2*dis[i]);
}
else if(que.size()&&que.top()>2*dis[i]){
now-=que.top();
que.pop();
now+=2*dis[i];
que.push(2*dis[i]);
}
else break ;
}
}
for(int i=mid+1;i<=q-1;i++){
if(!a[i]) continue ;
for(int j=1;j<=a[i];j++){
if(now+2*dis[i]<=i-1){
mx++;
now+=2*dis[i];
que.push(2*dis[i]);
}
else if(que.size()&&que.top()>2*dis[i]){
now-=que.top();
que.pop();
now+=2*dis[i];
que.push(2*dis[i]);
}
else break ;
}
}
a[mid]++;
}
ans=-mx;
for(int i=1;i<=n;i++)
if(a[i]!=-1) ans+=a[i];
return Print(ans);
}
#include<ctime>
int main(){
//#define LOCAL
#ifdef LOCAL
int st=clock();
#endif
Init();
Solve();
#ifdef LOCAL
int en=clock();
printf("cost %d ms\n",en-st);
#endif
return 0;
}
```