【NOIP2015普及组复赛】题4：推销员

题4：推销员

【题目描述】

阿明是一名推销员，他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住户。螺丝街一共有 N N N 家住户，第 i i i 家住户到入口的距离为 S i S_i Si​ 米。由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。阿明会从入口进入，依次向螺丝街的 X X X 家住户推销产品，然后再原路走出去。

阿明每走 1 1 1 米就会积累 1 1 1 点疲劳值，向第 i i i 家住户推销产品会积累 A i A_i Ai​ 点疲劳值。阿明是工作狂，他想知道，对于不同的 X X X，在不走多余的路的前提下，他最多可以积累多少点疲劳值。

【输入】

第一行有一个正整数 N N N，表示螺丝街住户的数量。

接下来的一行有 N N N 个正整数，其中第 i i i 个整数 S i S_i Si​ 表示第 i i i 家住户到入口的距离。数据保证 S 1 ≤ S 2 ≤ … ≤ S n < 1 0 8 S_1≤S_2≤…≤S_n<10^8 S1​≤S2​≤…≤Sn​<108。

接下来的一行有 N N N 个正整数，其中第 i i i 个整数 A i A_i Ai​ 表示向第 i i i 户住户推销产品会积累的疲劳值。数据保证 A i < 1 0 3 A_i<10^3 Ai​<103。

【输出】

输出 N N N 行，每行一个正整数，第 i i i 行整数表示当 X = i X=i X=i 时，阿明最多积累的疲劳值。

【输入样例1】

5
1 2 3 4 5
1 2 3 4 5

【输出样例1】

15
19
22
24
25

【样例1说明】

X = 1 : X=1: X=1:向住户 5 5 5 推销，往返走路的疲劳值为 5 + 5 5+5 5+5，推销的疲劳值为 5 5 5，总疲劳值为 15 15 15。

X = 2 : X=2: X=2:向住户 4 、 5 4、5 4、5 推销，往返走路的疲劳值为 5 + 5 5+5 5+5，推销的疲劳值为 4 + 5 4+5 4+5，总疲劳值为 5 + 5 + 4 + 5 = 19 5+5+4+5=19 5+5+4+5=19。

X = 3 : X=3: X=3:向住户 3 、 4 、 5 3、4、5 3、4、5 推销，往返走路的疲劳值为 5 + 5 5+5 5+5，推销的疲劳值 3 + 4 + 5 3+4+5 3+4+5，总疲劳值为 5 + 5 + 3 + 4 + 5 = 22 5+5+3+4+5=22 5+5+3+4+5=22。

X = 4 : X=4: X=4:向住户 2 、 3 、 4 、 5 2、3、4、5 2、3、4、5 推销，往返走路的疲劳值为 5 + 5 5+5 5+5，推销的疲劳值 2 + 3 + 4 + 5 2+3+4+5 2+3+4+5，总疲劳值 5 + 5 + 2 + 3 + 4 + 5 = 24 5+5+2+3+4+5=24 5+5+2+3+4+5=24。

X = 5 : X=5: X=5: 向住户 1 、 2 、 3 、 4 、 5 1、2、3、4、5 1、2、3、4、5 推销，往返走路的疲劳值为 5 + 5 5+5 5+5，推销的疲劳值 1 + 2 + 3 + 4 + 5 1+2+3+4+5 1+2+3+4+5，总疲劳值 5 + 5 + 1 + 2 + 3 + 4 + 5 = 25 5+5+1+2+3+4+5=25 5+5+1+2+3+4+5=25。

【输入样例2】

5
1 2 2 4 5
5 4 3 4 1

【输出样例2】

12
17
21
24
27

【样例2说明】

X = 1 ： X=1： X=1：向住户 4 4 4 推销，往返走路的疲劳值为 4 + 4 4+4 4+4，推销的疲劳值为 4 4 4，总疲劳值 4 + 4 + 4 = 12 4+4+4=12 4+4+4=12。

X = 2 ： X=2： X=2：向住户 1 、 4 1、4 1、4 推销，往返走路的疲劳值为 4 + 4 4+4 4+4，推销的疲劳值为 5 + 4 5+4 5+4，总疲劳值 4 + 4 + 5 + 4 = 17 4+4+5+4=17 4+4+5+4=17。

X = 3 ： X=3： X=3：向住户 1 、 2 、 4 1、2、4 1、2、4 推销，往返走路的疲劳值为 4 + 4 4+4 4+4，推销的疲劳值为 5 + 4 + 4 5+4+4 5+4+4，总疲劳值 4 + 4 + 5 + 4 + 4 = 21 4+4+5+4+4=21 4+4+5+4+4=21。

X = 4 ： X=4： X=4：向住户 1 、 2 、 3 、 4 1、2、3、4 1、2、3、4 推销，往返走路的疲劳值为 4 + 4 4+4 4+4，推销的疲劳值为 5 + 4 + 3 + 4 5+4+3+4 5+4+3+4，总疲劳值 4 + 4 + 5 + 4 + 3 + 4 = 24 4+4+5+4+3+4=24 4+4+5+4+3+4=24。或者向住户 1 、 2 、 4 、 5 1、2、4、5 1、2、4、5 推销，往返走路的疲劳值为 5 + 5 5+5 5+5，推销的疲劳值为 5 + 4 + 4 + 1 5+4+4+1 5+4+4+1，总疲劳值 5 + 5 + 5 + 4 + 4 + 1 = 24 5+5+5+4+4+1=24 5+5+5+4+4+1=24。

X = 5 ： X=5： X=5：向住户 1 、 2 、 3 、 4 、 5 1、2、3、4、5 1、2、3、4、5 推销，往返走路的疲劳值为 5 + 5 5+5 5+5，推销的疲劳值为 5 + 4 + 3 + 4 + 1 5+4+3+4+1 5+4+3+4+1，总疲劳值 5 + 5 + 5 + 4 + 3 + 4 + 1 = 27 5+5+5+4+3+4+1=27 5+5+5+4+3+4+1=27。

【数据说明】

对于 20 % 20\% 20% 的数据， 1 ≤ N ≤ 20 1≤N≤20 1≤N≤20；

对于 40 % 40\% 40% 的数据， 1 ≤ N ≤ 100 1≤N≤100 1≤N≤100；

对于 60 % 60\% 60% 的数据， 1 ≤ N ≤ 1000 1≤N≤1000 1≤N≤1000；

对于 100 % 100\% 100% 的数据， 1 ≤ N ≤ 100000 1≤N≤100000 1≤N≤100000。

【代码如下】：

#include<bits/stdc++.h>
using namespace std;
//ifstream cin("salesman.in");
//ofstream cout("salesman.ans"); 
const int maxn=100000;
struct node{
    int s;
    int v;
    bool operator < (node a)const
    {
        return v<a.v;
    }
}e[maxn],s;
priority_queue<node> q;
int n,ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>e[i].s;
    for(int i=1;i<=n;i++)
    cin>>e[i].v;
    s.s=s.v=0;
    q.push(s);
    int now=0,maxx=0;
    for(int i=1;i<=n;i++){
        int next=now;
        s=q.top();
        maxx=s.v;
        for(int j=now+1;j<=n;j++)//寻找now以后的最优房屋
        if(e[j].v+(e[j].s-e[now].s)*2>maxx){
            maxx=e[j].v+(e[j].s-e[now].s)*2;
            next=j;
        }
        e[next].v+=(e[next].s-e[now].s)*2;//更新
        if(now!=next)
        q.push(e[next]);//入队
        for(int j=now+1;j<next;j++)//now到next之间的房屋入队
        q.push(e[j]);
        s=q.top();//弹出队位
        ans+=s.v;//加入答案
        q.pop();
        cout<<ans<<endl;//输出
        now=next;//now=next继续寻找最优值
    }
    return 0;
}