P2672推销员

柔情只为你懂 2021-11-11 01:46 229阅读 0赞

[传送][Link 1]

![1605842-20190703085032460-268631954.png][]

![1605842-20190703085046211-786421409.png][]

![1605842-20190703085059049-1662534687.png][]

![1605842-20190703085113099-66776010.png][]

![1605842-20190703085121945-1580386019.png][]

很抱歉之前用错误的思路写了一篇题解ρωρ

先说一下之前的思路。

对于每个住户，求出它的s\[i\]\*2+a\[i\],寻找最大的住户m，然后按照a排序，如果m在前x大的住户里面，就选择前x大的住户,从中选择最大的s，计算答案。否则选择权值前x-1大的住户和m。

but这个是错的！！！！

hack数据：

1 5 6

3 5 2

正确答案：15 19 22

上述思路的答案：15 18 22

第二个按照上述思路的选法：选择第1,2户。

正解选法：选择第2,3户。

错误思路的代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    int n,sum[100009],ma[400009];
    struct zh{
        int bh,l,p,q;
    }r[100009];
    int read()
    {
        char ch=getchar();
        int x=0;bool f=0;
        while(ch<'0'||ch>'9')
        {
            if(ch=='-')f=1;
            ch=getchar();
        }
        while(ch>='0'&&ch<='9')
        {
            x=(x<<3)+(x<<1)+(ch^48);
            ch=getchar();
        }
        f?x=-x:x=x;
        return x;
    }
    bool cmp1(zh a,zh b)
    {
        return a.p>b.p;
    }
    int main()
    {
        int maxn=0,maxi;
        n=read();int m;
        for(int i=1;i<=n;i++)
         r[i].l=read(),r[i].bh=i;
        for(int i=1;i<=n;i++)
         {
             r[i].p=read();
             r[i].q=r[i].l*2+r[i].p;
             if(r[i].q>maxn)
              maxn=r[i].q,maxi=r[i].bh;
         }
         m=r[n].l;
         sort(r+1,r+1+n,cmp1);
         for(int i=1;i<=n;i++)
           sum[i]=sum[i-1]+r[i].p,ma[i]=max(ma[i-1],r[i].l);
         int mi;
         for(int i=1;i<=n;i++)
         {
             if(r[i].bh==maxi)
             {
                 mi=i;
                 break;
            }
         }
         printf("%d\n",maxn);
         for(int i=2;i<n;i++)
         {
          int ren=0,lu=r[mi].l*2;
             if(mi<=i)
             {
                 ren=sum[i];
             if(ma[i]>r[mi].l)lu=ma[i]*2;
             int ans=ren+lu;
             printf("%d\n",ans);
            }
            else
            {    ren=r[mi].p+sum[i-1];
             if(ma[i-1]>r[mi].l)lu=ma[i-1]*2;
             int ans=ren+lu;
             printf("%d\n",ans);
            }
         }
         int ans=0;
         for(int i=1;i<=n;i++)
           ans+=r[i].p;  
           ans+=m*2;
           printf("%d\n",ans);
    }

它是个错的QAQ

正确的思路是什么鸭？窝也不会鸭~来让我们仔(fan)细(fan)思(ti)考(jie)

先来说一下上面的思路错在哪里。

上面对于每个x,都有一种确定的方案（选前x个或者选前x-1个）。但是我们不知道另一种方案是否比我们确定的这个方案要优。

所以我们把上面的两种选法比较一下。

先按照a从大到小排序

用qaq\[i\]来记录后i个住户里面最大的a\[i\]+s\[i\]\*2（排序后），sum\[i\]是排序后的前缀和，ma\[i\]是排序后前i个中的最大的s,则ansi=max(sum\[x\]+ma\[i\]\*2,sum\[x-1\]+qaq\[x\])

为什么qaq是记录后i个住户的信息呢？

因为后i个住户的a会小，但是s可能会很大。这里是考虑s对ans的影响

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    int n,sum[100009],ma[400009],qaq[400009];
    struct zh{
        int bh,l,p,q;
    }r[100009];
    int read()
    {
        char ch=getchar();
        int x=0;bool f=0;
        while(ch<'0'||ch>'9')
        {
            if(ch=='-')f=1;
            ch=getchar();
        }
        while(ch>='0'&&ch<='9')
        {
            x=(x<<3)+(x<<1)+(ch^48);
            ch=getchar();
        }
        f?x=-x:x=x;
        return x;
    }
    bool cmp1(zh a,zh b)
    {
        return a.p>b.p;
    }
    int main()
    {
        int maxn=0,maxi;
        n=read();int m;
        for(int i=1;i<=n;i++)
         r[i].l=read(),r[i].bh=i;
        for(int i=1;i<=n;i++)
         {
             r[i].p=read();
             r[i].q=r[i].l*2+r[i].p;
             if(r[i].q>maxn)
              maxn=r[i].q,maxi=r[i].bh;
         }
         m=r[n].l;
         sort(r+1,r+1+n,cmp1);
         for(int i=1;i<=n;i++)
           sum[i]=sum[i-1]+r[i].p,ma[i]=max(ma[i-1],r[i].l);
         qaq[n]=r[n].l*2+r[n].p;
         for(int i=n-1;i>=1;i--)
            qaq[i]=max(qaq[i+1],r[i].l*2+r[i].p);
         
         printf("%d\n",maxn);
         for(int i=2;i<n;i++)
         {
            int ans=max(sum[i]+ma[i]*2,sum[i-1]+qaq[i]);
            printf("%d\n",ans);
         }
         int ans=0;
         for(int i=1;i<=n;i++)
           ans+=r[i].p;  
           ans+=m*2;
           printf("%d\n",ans);
    }

它终于对了

转载于:https://www.cnblogs.com/lcez56jsy/p/11124252.html

[Link 1]: https://www.luogu.org/problemnew/show/P2672
[1605842-20190703085032460-268631954.png]: /images/20211109/7b2255cf54f84ad2ac7c7431544de8e9.png
[1605842-20190703085046211-786421409.png]: /images/20211109/6decad66841a4f57903d93620aa21e78.png
[1605842-20190703085059049-1662534687.png]: /images/20211109/6a5aedac6c1a4cd498f5d4977516c09f.png
[1605842-20190703085113099-66776010.png]: /images/20211109/dd0a7a5069a14603ad00be8ab2c16988.png
[1605842-20190703085121945-1580386019.png]: /images/20211109/30d9480dbba549e298a74741509eb452.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211109/d02403d23d8742d790bf1171bd1fd02c.png