推销员

题目描述

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

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

输入输出格式

输入格式：

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

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

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

输出格式：

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

输入输出样例

输入样例#1： 复制

5
1 2 3 4 5
1 2 3 4 5

输出样例#1： 复制

15
19
22
24
25

输入样例#2： 复制

5
1 2 2 4 5
5 4 3 4 1

输出样例#2： 复制

12
17
21
24
27

说明

【输入输出样例 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。

【输入输出样例 2 说明】

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

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

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

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

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

总疲劳值 5+5+5+4+3+4+1=27。

【数据说明】

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

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

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

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

//这其实是一道非常简单的贪心
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct tui
{
    int s,val;
}a[100004];//s和val分别表示题目中的
bool cmp(tui a,tui b)
{
    return a.val>b.val;
}//把每户人家的疲劳值从大到小排序，为什么这么做下面我会详细解释

int i,j,ans,maxx,n,k;
int main()
{
   	scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i].s);
    }
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i].val);
    }
    sort(a+1,a+n+1,cmp);//以上是输入数据和排序,这是我一直说的sort函数，不会的百度。 
    for(i=1;i<=n;i++)
    {
        if(2*a[i].s+a[i].val>maxx)
        {
            j=k=i;
            maxx=2*a[i].s+a[i].val;
        }
}//我从这里开始解释我的思路吧，上面这个for循环是找出x=1的答案，因为去到答案的人家还要走回来，所以要2*a[i].s //因为每一户还有一个疲劳值，所以要加上a[i].val，至于j和k，只是为了我方便而已，下面我会解释

   ans+=maxx;
   printf("%d\n",ans);//输出第一个答案
   for(i=1;i<=n;i++)
   {
       if(i==k)//因为刚刚我们已经用k记录了最大的疲劳值，所以遇到k，我们就跳过，不加上了
       {
           continue;
       }
       if(a[j].s<a[i].s)//如果某一个户答案人家的距离比k的更大，那我们就减去k家的距离而加上现在这户i家的距离，因为我们贪心
//的思路是每次找某户疲劳值最大的人家(就是val），所以当我们经过i，就一定会k（还不明白的我也很难说清，画图看看吧）
//不给走重复路，所以就要这样做了
        {
            ans=ans-2*a[j].s+2*a[i].s;
            j=i;//修改当前最远的答案距离
            ans+=a[i].val;
            printf("%d\n",ans);
        }
        else//因为i在j之前，所以经过j就一定会经过i
        {
            ans+=a[i].val;
            printf("%d\n",ans);
        }
   }
}