题目描述

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

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

输入

输入格式：

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

接下来的一行有 N 个正整数，其中第 i个整数 Si 表示第 i 家住户到入口的距离。数据保证 S_1≤S_2≤…≤S_n<10^8

接下来的一行有 NN 个正整数，其中第 ii 个整数 A_iAi 表示向第 ii 户住户推销产品会积累的疲劳值。数据保证 Ai<1000 。

说明

【输入输出样例1说明】

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

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

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

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

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

【数据说明】

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

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

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

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

输出

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

样例输入

5

1 2 3 4 5

1 2 3 4 5

样例输出

15

19

22

24

25

思路

贪心算法

我们把题目分解成要求在每一种条件下，求最小疲劳值

对于一种条件来说，当前条件下选取最优解

代码：

#include<bits/stdc++.h>

using namespace std;

struct f{//设置结构体

       int s,v;

}x[100005];

bool cmp(f a,f b)

{

       return a.v>b.v;

}

int main()

{

       int n,p[100005],q[100005],t[100005];

       cin>>n;

       for(int i=1;i<=n;i++)

       cin>>x[i].s;//输入距离

       for(int i=1;i<=n;i++)

       cin>>x[i].v;//输入疲劳值

       sort(x+1,x+1+n,cmp);//以疲劳值从大到小排序

       for(int i=n;i>=1;i--)

       {

              p[i]=max(p[i+1],2*x[i].s+x[i].v);//取单次最优解，,2*x[i].s+x[i].v)表示第i个房子来回的路程疲劳值加上推销疲劳值，p[i+1]表示1~i+1所有一起跑的疲劳值

       }

       for(int i=1;i<=n;i++)

       {

              q[i]=max(q[i-1],x[i].s);//选取每一次路程疲劳值中的最大值

       }

       for(int i=1;i<=n;i++)

       {

              t[i]=t[i-1]+x[i].v;//前i次推销疲劳值的累加

       }

       for(int i=1;i<=n;i++)

       {

              printf("%d\n",max(t[i-1]+p[i],t[i]+2*q[i]));//输出每一种情况下的最优解

       }

}