贪心模拟
先从这个样例开始讲解吧
6
1 2 3 4 5 6
4 2 3 5 3 1
若当前$X = 1$,那么我们可以建一个$F$数组
$F[i]$ 表示从入口进去再出来,新添加第 $a[i]$ 家用户推销,不走多余路,会对答案的贡献
用 $ans$ 表示当前答案
用 $now$ 表示走的最远的点
那么$X = 1$ 时: $F[i] = s[i]*2+a[i]$
$F =$ {$6, 6, 9, 13, 13, 13$}
所以我们从 $F[i]$ 中挑选一个最大值就好了
将$now = max.id$ 即 $now = 4$ (其实5或6也可以)
$ans$ += $F[4]$
($ans$ == $13$)
那么想一想,这将对其他 $F[i]$ 造成什么影响?
在考虑 $X = 2$ 时.
若 $s[i]$ < $s[now]$也就是在 $s[now]$的左侧
$F[i]$ = $a[i]$
因为可一在去 $now$ 点的路上推销
补充: 其实先去推销 $i$ 点和先去推销 $now$ 点的疲惫值是一样的
则$F$ 变为{$4, 2, 3, /, 13, 13$}
若 $s[i]$ > $s[now]$也就是在 $s[now]$的右侧
$F[i] = (s[i]-s[now])*2+a[i]$
因为可以在原本的路程上往前多走二段路程($s[i]-s[now]$) $*2$ (一去一回)
所以$F$变为{$4, 2, 3, /, 5, 5$}
现在,我们再次从 $F$数组中找出最大值的ID
令 $now = 6$ ( $5$ 也可以 )
$ans$ += F[6]
($ans$ == $18$)
这时
$F$ = {$4, 2, 3, /, 3, /$}
$F[5]$ 变成了 $3$ ,因为它在 $6$ 左边
右侧没有点了,所以不更新 $F$ 值
$X = 3$ 时
$ans$ += F[1]
($ans$ == $22$)
$F$ = {$/, 2, 3, /, 3, /$}
$X = 4$ 时
$ans$ += F[3]
($ans$ == $25$)
$F$ = {$/, 2, /, /, 3, /$}
$X = 5$ 时
$ans$ += F[5]
($ans$ == $28$)
$F$ = {$/, 2, /, /, /, /$}
$X = 6$ 时
$ans$ += F[2]
($ans$ == $30$)
$F$ = {$/, /, /, /, /, /$}
最终答案为:
13
18
22
25
28
30
那么问题来了,如何快速找出最大值呢
我们使用 $maxn[now]$ 表示 $now$ ~ $n$ 中 $F[i]$ 的最大值 ($now < i <= n$)
$maxn[i]$ 的作用是维护 $now$ 右侧的 $F[i]$ 的最大值
那么 $now$ 左侧的最大$a[i]$ 之怎么维护捏?
因为 $now$ 左侧的值需要有删除最大值的操作
那么不能使用类似 $maxn$ 的预处理操作
但 priority_queue 是一个不错的数据结构
可以用优先队列 $q$ 维护左侧最大 $a[i]$ 的值
会发现,这些操作都不会用到 $F$ 数组,所以不需要建立此数组,更不需要更改它,
$now$ 左侧的 $a[i]$ 都不会改变了,而右侧的 $maxn[now]$ 只需要减掉 $s[now]2$ 即可
$maxn[now]$ = $s[i]2+a[i]$ , ( i$ 是此时的最大值)
所以 $maxn[now]-s[now]2$ = $a[i]+s[i]2-s[now]2$ = $a[i]+(s[i]-s[now])2$ 也就是上述 $F[i]$ 的值
Ac Code:
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10,INF=1e9,mod=INF+7;
int n,now,cnt;
long long ans;
int a[N],s[N];
pair<int,int> maxn[N];
priority_queue<int> q;
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;i++)
scanf("%d",s+i);
for(int i = 1;i <= n;i++)
scanf("%d",a+i);
maxn[n+1].second = -INF;
for(int i = n;i >= 1;i--){
maxn[i] = maxn[i+1];
if(s[i]*2+a[i] >= maxn[i].second)
maxn[i] = make_pair(i,s[i]*2+a[i]);
}
for(int i = 1;i <= n;i++){
int l = (q.empty() ? -INF : q.top());
int r = (now == n ? -INF : maxn[now+1].second);
if(l >= r-s[now]*2){
ans += l;
q.pop();
printf("%lld\n",ans);
}else {
ans += r-s[now]*2;
for(int i = now+1;i <= maxn[now+1].first-1;i++)
q.push(a[i]);
now = maxn[now+1].first;
printf("%lld\n",ans);
}
}
return 0;
}