谈谈心路历程:
模拟完样例后直觉挑出合法的最大和最小(不在一个包里)
让最小减去最大,然后如果最小所在的集合只有它自己的话,就可以开始疯狂堆了。
但样例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); }