codeforces 1467C. Three Bags

谈谈心路历程:

模拟完样例后直觉挑出合法的最大和最小(不在一个包里)

让最小减去最大,然后如果最小所在的集合只有它自己的话,就可以开始疯狂堆了。

但样例2告诉我们可能最小所在的集合可能不只有自己,那么最小的小伙伴一定要被吃掉。

我们就要在剔除前面已经用过的两个数的情况下,再跑一次上述流程。

理论上是对的,实现起来我不会写。

在写的算法又长又烂的过程中,发现:

-a-b+abs(a-b)等价于-min(a,b)*2;

那么取最大那步可以去掉了。

再紧接着,怎么优化如果最小的集合不只有自己的情况?

标解是暴力。

我对暴力有了更深的理解——管它什么情况,统统算一下取极值好了!

这就是6种情况的由来:

其中ans-min1*2-min2*2....,指的就是最小所在的集合不只有自己,要再凑一个;

而ans1+ans2-ans3,就是最小所在的集合只有自己,通过模拟发现这样操作实际上只有最小的贡献是负的。

坑点是:

#不开longlong见祖宗

#final=max(final,xxx)

不能写成final=max(xxx,yyy;

再final=max(zzz,ppp);

..(我的问题

#include<bits/stdc++.h>
using namespace std;
int main( )
{ long long a,b,c,ans=0,ans1=0,ans2=0,ans3=0,m1,m2,m3;
  // freopen("lys.in","r",stdin);
   
 cin>>a>>b>>c;
 m1=m2=m3=0x3f3f3f3f;
    for(int i=1;i<=a;i++)
     {
         long long x;
         cin>>x;
         ans1+=x;
         ans+=x;
         m1=min(m1,x);
     }
     
     for(int i=1;i<=b;i++)
     {
         long long x;
         cin>>x;
         ans2+=x;
         ans+=x;
         m2=min(m2,x);
     }
     
     for(int i=1;i<=c;i++)
     {
         long long x;
         cin>>x;
         ans3+=x;
         ans+=x;
         m3=min(m3,x);
     }
     
    long long final;
     final=max(max(ans-m1*2-m3*2,ans-m2*2-m3*2),ans-m1*2-m2*2);
     final=max(final,max(max(ans1+ans2-ans3,ans2+ans3-ans1),ans1+ans3-ans2));
     //q p t
     printf("%lld\n",final);
}

 

上一篇:Heat编排服务


下一篇:泛型