题目

题目大意

阿明是一名推销员……螺丝街是一条直线，一端有入口，一共有 \(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]\)，选值最大的一个点即为答案。

假设你已经选了一些点，其中有一个最右端的点 \(i\)，如果在其左方再选一个点，推销员只要在路上“顺带”推销一下而无需增加行走路程，那么你选了这个点总疲劳值就增加 \(a[i]\)。

同理，在右边选一个点 \(j\)，要多走来回 \(2*(s[j]-s[i])\) 的路程，也就是增加这么多的疲劳值。

于是，每次选择点时，取出左边疲劳值最大的点，枚举 \(i\) 右边的点找出边疲劳值最大的，两个比较，取大值。发现左边只要无脑取最大就好了，所以左边的点可以用堆维护。

如果左边的大，则直接弹出堆，否则将 \(now\)（最右点距离）更新，把 \(now+1...new\_now-1\) 之间的点的 \(a[i]\) 扔进堆里即可。时间复杂度，最好情况下是 \(O(nlogn)\)，最坏情况下是 \(O(n2)\)，数据比较平均，所以能得满分。

代码(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;
}

【NOIP2015普及组】推销员

原文：https://www.cnblogs.com/1024th/p/10473888.html