P2672 推销员

    • 2.3K通过
    • 6.5K提交
  • 题目提供者 CCF_NOI
  • 评测方式 云端评测
  • 标签 树状数组 线段树 贪心 NOIp普及组 2015 高性能
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

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

    输入输出格式

    输入格式:

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

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

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

    输出格式:

    输出 $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$ 。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。