P2672 推销员-白红宇

P2672 推销员

阅读量：5340 次

发布时间：2019-06-15

本文共 1642 字，大约阅读时间需要 5 分钟。

题目描述

阿明是一名推销员，他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住户。螺丝街一共有

阿明每走

输入输出格式

输入格式：

第一行有一个正整数

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

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

输出格式：

输出

$输入样例1：$

51 2 3 4 51 2 3 4 5

输出样例1：

1519222425

输入样例2：

51 2 2 4 55 4 3 4 1

输出样例2：

1217212427

思路：

首先，我们可以推出，当现在需要选x家的时候一定包含了x-1家的选择，也就是我们把问题化为了如何从x-1推到x。我们可以从1、保留前x-1个，从之后的住户中选一个A+S*2最大的。2、保留前x-1个，选择第x个，并且在前x个中选择一个S*2最大的。 >>这两个选择中选择一个更大的。

解析：

我们先按照每一家的A[i]进行降序排列，sum[]表示i的前缀和，msum[]表示在前i家中S*2最大值，h[]表示在后n-i+1家中A+S*2最大的一家(选择2)。

代码：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int n,sum[100008],msum[100008],h[100008];struct D{    int s,a;}d[100008];int cmp(D x,D y){    return x.a>y.a;}long long read(){    long long x=0,f=1;    char ch=getchar();    while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}int main(){    n=read();    for(int i=1;i<=n;++i) d[i].s=read();    for(int i=1;i<=n;++i) d[i].a=read();    sort(d+1,d+n+1,cmp);    for(int i=1;i<=n;++i) sum[i]=sum[i-1]+d[i].a;    for(int i=1;i<=n;++i) msum[i]=max(msum[i-1],d[i].s);    for(int i=n;i>=1;--i) h[i]=max(h[i+1],d[i].s*2+d[i].a);    for(int i=1;i<=n;++i) printf("%d\n",max(sum[i-1]+h[i],sum[i]+msum[i]*2));    return 0;}

转载于:https://www.cnblogs.com/-hhs/p/11005480.html

你可能感兴趣的文章