本贴最后更新于 360 天前,其中的信息可能已经天翻地覆

题目描述

阿明是一名推销员,他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同,出口与入口是同一个,街道的一侧是围墙,另一侧是住户。螺丝街一共有 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);
        }
   }
}

感谢    关注    收藏    赞同    反对    举报    分享