题目描述

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

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

输入描述:

第一行有一个正整数N，表示螺丝街住户的数量。
接下来的一行有N个正整数，其中第i个整数表示第i家住户到入口的距离。数据保证。
接下来的一行有N个正整数，其中第i个整数表示向第i户住户推销产品会积累的疲劳值。数据保证。

输出描述:

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

示例1

输入
5
1 2 3 4 5
1 2 3 4 5
输出
15
19
22
24
25
说明
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

输入
5
1 2 2 4 5
5 4 3 4 1
输出
12
17
21
24
27
说明
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。

解答

这道题我用的是贪心的算法，对于每个疲劳值都定义一个数组，算法的步骤很显然即为：一开始定义sum=0，每一步都计算出能够增加的最大的疲劳值maxn，将sum+=maxn，输出，并将这个点从表中删除。

那么最大的利益maxn如何计算呢？

很显然，一开始的maxn即为距离（a数组）+推销的疲劳值（j）。但接下来公式即不同了。

我们将当前被选中的点的距离称为this，之前的最大点的距离称为prev。那么就会有两种情况：

1.this>prev，也就是当前到达的是一个新的，距离比之前更远的点，那么新增的疲劳值即为；

2.this<prev，也就是当前点的距离包含在之前走过的距离内，那么新增的疲劳值即为j。

最后还有几点需要考虑：

1.考虑到可能会有几户人家的推销疲劳值相同，则我们需要额外开一个数组来存储。而在删除点时只需将这个数组的值自减即可；

2.我们每次搜索时都要保存下maxn所对应的疲劳值和最大距离；

3.需要建立一个根据推销疲劳值来存储人家的数组。 

#include <iostream>
using namespace std;
int n,maxn,sum,a[100001],b[100001],c[100001][101],t,p=0,x,y;
int main()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<=n;i++)
    {
        cin>>t;
        b[t]++;//存储每种疲劳值有几户人家
        c[t][b[t]]=i; //根据疲劳值找户 
    }
    for (int i=1;i<=n;i++)
    {
        maxn=0;x=0;y=0;
        for (int j=0;j<=999;j++)
          if (b[j]>0)
            if (a[c[j][b[j]]]>p&&(a[c[j][b[j]]]-p)*2+j>maxn)//如果当前点大于之前最大点
            {
                maxn=(a[c[j][b[j]]]-p)*2+j;//计算增加的疲劳值
                x=j;  
                y=a[c[j][b[j]]]; 
            }
            else if (a[c[j][b[j]]]<=p&&j>maxn)//小于
            {
                maxn=x=j;  
                y=p;
            }
            p=y;b[x]--;//记录最大点，删除当前点
            sum+=maxn;//累加
            cout<<sum<<endl;//输出
    }
    return 0;
}


来源：24680esz