P2672 推销员（已经补锅）

P2672 推销员

下面讲正确的贪心

题解

考虑当推销员要推销 i 家客户时，他可以有两种选择：

（1）选择前 i 家疲劳值 a 最大的客户，加上这些客户里最远的距离

（2）选择前 i-1 家疲劳值 a 最大的客户，然后从后边找一个距离最远的客户

所以贪心思路就出来了

考虑维护什么？

反正怎样都是与疲劳值息息相关，那不如先按照疲劳值从大到小sort一下好了

then

sum[ i ]  前 i 个疲劳值最大的客户，疲劳值之和

x[ i ]  前 i 个疲劳值最大的客户中（也就是sum[ i ]中），距离起点最远的那个客户的距离

hou[ i ]  （sort之后）后 i 个客户中单独推销最大的那个客户的 单推值（=距离*2+疲劳值）

对于每一个 i ，ans就是：

max（sum[ i-1 ]+hou[ i ] , sum[ i ]+q[ i ]）

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5+;

int n;

int sum[maxn],hou[maxn],x[maxn];

struct node

{

    int s,a;

}peo[maxn];

bool cmp(node x,node y)

{

    return x.a >y.a ;

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)

      scanf("%d",&peo[i].s );

    for(int i=;i<=n;i++)

      scanf("%d",&peo[i].a );

    sort(peo+,peo+n+,cmp);

    for(int i=;i<=n;i++)

    {

        sum[i]=sum[i-]+peo[i].a ;

        x[i]=max(x[i-],peo[i].s* );

    }

    for(int i=n;i>=;i--)

      hou[i]=max(hou[i+],peo[i].s*+peo[i].a );

    for(int i=;i<=n;i++)

    {

        printf("%d\n",max(sum[i-]+hou[i],sum[i]+x[i]));

    }

    return ;

}

后记

带坏萌新

这题数据好水啊，一个错误的贪心井然可以AC

一个nice数据可以卡死这个错误代码

有Bug：测试数据为：5 1 2 4 2 5 5 4 4 3 2

正确输出:12 17 21 25 28

下面这个程序的输出：12 17 21 24 28

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5+10;

int n,k,rode;

long long ans=0;

struct node

{

    int s,a,dt;

}peo[maxn];

bool cmp(node x,node y)

{

    return x.a >y.a ;

}

int main()

{

    scanf("%d\n",&n);

    if(n==1)

    {

        int x,y;

        scanf("%d\n",x*2+y);

        return 0;

    }

    for(int i=1;i<=n;i++)

      scanf("%d",&peo[i].s );

    for(int i=1;i<=n;i++)

    {

        scanf("%d",&peo[i].a );

        peo[i].dt =peo[i].s *2+peo[i].a ;

        if(peo[i].dt>ans)

        {

            ans=peo[i].dt ;

            k=i;

        }

    }

    printf("%ld\n",ans);

    rode=peo[k].s;

    peo[k].a =-1;

    sort(peo+1,peo+n+1,cmp);

    for(int i=1;i<n;i++)

    {

        if(peo[i].s <=rode )

        {

            ans+=peo[i].a ;

            printf("%ld\n",ans);

        }

        else

        {

            ans+=peo[i].a ;

            ans-=rode*2;

            ans+=peo[i].s *2;

            rode=peo[i].s ;

            printf("%ld\n",ans);

        }

    }

    return 0;

}