题目
题目大意
阿明是一名推销员……螺丝街是一条直线，一端有入口，一共有 \(N(<100,000)\) 家住户，第 \(i\) 家住户到入口的距离为 \(S_i\) 米。由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。阿明会从入口进入，依次向螺丝街的 \(X\) 家住户推销产品，然后再原路走出去。
阿明每走 \(1\) 米就会积累 \(1\) 点疲劳值，向第 \(i\) 家住户推销产品会积累 \(A_i\) 点疲劳值。阿明是工作狂，他想知道，对于不同的 \(X\)， 在不走多余的路的前提下，他最多可以积累多少点疲劳值。
输入格式
第一行有一个正整数 \(N\)，表示螺丝街住户的数量。
接下来的一行有 \(N\) 个正整数，其中第 \(i\) 个整数 \(S_i\) 表示第 \(i\) 家住户到入口的距离。 数据保证 \(S_1 ≤S_2 ≤…≤S_n <10^8\) 。
接下来的一行有 \(N\) 个正整数，其中第 \(i\) 个整数 \(A_i\) 表示向第 \(i\) 户住户推销产品会积累的疲劳值。数据保证 \(A_i <10^3\) 。
输出格式
输出 \(N\) 行，每行一个正整数，第 \(i\) 行整数表示当 \(X=i\) 时，阿明最多积累的疲劳值。
样例
样例输入
5
1 2 3 4 5
1 2 3 4 5
样例输出
15
19
22
24
25
分析Ⅰ
假设左边为入口，越往右越深，每个住户设为一个点。
“不走多余的路”，就是从最左端向右走到最右边的住户，再返回。所以\(X=1\)时，任意一个 \(i\) 点的疲劳值都为\(s[i]*2+a[i]\)，选值最大的一个点即为答案。
假设你已经选了一些点，其中有一个最右端的点 \(now\)，如果在其左方再选一个点 \(i\)，推销员只要在路上“顺带”推销一下而无需增加行走路程，那么你选了这个点总疲劳值就增加 \(a[i]\)。
同理，在右边选一个点 \(j\)，增加的疲劳值为 \(2*(s[j]-s[now])+a[j]\)。
于是，每次选择点时，取出左边疲劳值最大的点，枚举 \(now\) 右边的点找出边疲劳值最大的，两个比较，取大值。发现左边只要无脑取最大就好了，所以左边的点可以用堆维护。
如果左边的大，则直接弹出堆，否则将 \(now\)（最右点）更新，把 \(now+1...new\_now-1\) 之间的点的 \(a[i]\) 扔进堆里即可。时间复杂度，最好情况下是 \(O(nlogn)\)，最坏情况下是 \(O(n^2)\)，数据比较平均，所以能得满分。
代码Ⅰ(c++)
#include<cstdio>
#include<queue>
#define reg register
using namespace std;
priority_queue<int>ql; //左边的点
int n;
int a[100005],s[100005];
int main(){
scanf("%d",&n);
int xi=0,ans=0;
for(reg int i=1;i<=n;++i)scanf("%d",&s[i]);
for(reg int i=1;i<=n;++i)scanf("%d",&a[i]);
for(int i=1;i<=n;++i)if((s[i]<<2)+a[i]>ans){
ans=(s[i]<<1)+a[i];
xi=i;
}
printf("%d\n",ans); //x=1时的解
for(int i=1;i<xi;++i)ql.push(a[i]); //左边扔进堆里
int now=xi;
for(int i=2;i<=n;++i){
int lmax=0,rmax=0,ri=0;
if(!ql.empty())lmax=ql.top(); //左边最大
for(int j=now+1;j<=n;++j) if(((s[j]-s[now])<<1)+a[j] > rmax){
rmax=s[j]*2-s[now]*2+a[j]; //遍历右边找出最大
ri=j;
}
if(lmax>rmax){
ans+=lmax;
ql.pop(); //弹出堆
}else{
ans+=rmax;
for(int j=now+1;j<ri;++j)ql.push(a[j]); //左边扔进堆里
now=ri;
}
printf("%d\n",ans);
}
return 0;
}
分析Ⅱ
在Ⅰ的基础上，右边的点也用优先队列维护。
代码Ⅱ(c++)
#include <iostream>
#include <cstdio>
#include <queue>
#define MN 100005
#define R register
using namespace std;
int n,s[MN],a[MN];
int now,maxL,ans;
struct Node{
int num,tired;
bool operator<(const Node& a)const{return tired<a.tired;}
}node,maxR;
priority_queue<Node>qR;
priority_queue<int>qL;
inline int ri(){
char c=getchar();int x=0,w=1;
while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
while( isdigit(c)){x=(x<<3)+(x<<1)+c-48;c=getchar();}
return x*w;
}
int main(){
n=ri();
for(R int i=1;i<=n;i++)s[i]=ri();
for(R int i=1;i<=n;i++)a[i]=ri();
for(R int i=1;i<=n;i++)node.num=i,node.tired=2*s[i]+a[i],qR.push(node); //记个编号num
for(R int i=1;i<=n;i++){
maxL=maxR.tired=0;
if(!qL.empty())maxL=qL.top();
while(!qR.empty()&&qR.top().num<=now)qR.pop(); //弹出右边不符合要求的点
if(!qR.empty())maxR=qR.top();
if(maxL<maxR.tired-2*s[now]){
ans+=maxR.tired-2*s[now];
for(R int k=now+1;k<maxR.num;k++)qL.push(a[k]);
now=maxR.num;
qR.pop();
}
else ans+=maxL,qL.pop();
printf("%d\n",ans);
}
return 0;
}