Ex - Bow Meow Optimization

当\(n,m\)都为偶数时，记狗的正中为\(x\)吗，猫的正中为\(y\)（正中在序列中就处于两个位置之间，不与任何位置重合）

一只猫\(i\)到\(x\)隔了\(C\)只狗，那么这只猫对应的代价就为\(B_i\times (\frac n2+C-(\frac n2-C))=B_i\times2C\)，狗的代价同理

那么对于\(x\)与\(y\)之间的\(0\)和\(1\)，它们随意交换位置都不影响\(x\)和\(y\)，所以我们可以将\(x\)到\(y\)的这段区间变为\(x111...000y\)，这时代价是最小的，然后我们发现，将\(x\)和\(y\)移动到\(1\)和\(0\)的交接处，重合，也是合法的

所以当\(n,m\)都是偶数时，其正中重合，也就是说，前一半序列中有\(\frac n2\)只狗和\(\frac m2\)只猫

当\(n\)或\(m\)有奇数时，让\(x\)左侧有\(\lfloor\frac n2\rfloor\)个\(0\)，\(y\)右侧有\(\lfloor\frac m2\rfloor\)个\(1\)，然后用上述方法，同样可以使得\(x\)和\(y\)重合

设\(d_i\)表示对于第\(i\)个位置上的\(0\)/\(1\)，其两侧\(1\)/\(0\)之差为多少，可以发现，在\(x\)与\(y\)重合的条件下，\(\sum d_i\)一定恒等于\(n\times m\)

证明：

考虑极端情况，序列呈\(00...11.|.11...00\)的分布情况，其中\(|\)表示\(x\)，\(0\)都集中在两端，\(1\)全部靠近\(|\)，此时的代价为\(n\times m\)

接下来，只需要证明，对于同一半内的相邻位置互换后，代价不变，大致分类讨论一下即可证得

因为\(\sum d_i\)恒定，所以要想\(\sum A_i/B_i\times d_i\)最小，就得让越大的\(A_i/B_i\)分配到越少的\(d_i\)

所以当\(n\)或\(m\)为奇数时，一定是将最大的那个\(A_i/B_i\)放到最中间，然后就可以将\(n\)和\(m\)都变为偶数

若\(n\%2==1\)时，所有\(1\)的左/右边实际上会比将\(n\)变为偶数后的序列多一个\(0\)，所以所有的\(1\)的\(d\)都要\(+1\)（当\(1\)在左半部分时，其右边的\(0\)的数量一定\(\geq\)其左边的\(0\)的数量，所以现在其右边又多出一个\(0\)后，\(d+1\)，\(1\)在右半部分时同理），\(m\%2==1\)同理。所以需要在一开始就给答案加上\(\sum A_i\)或\(\sum B_i\)

然后对所有\(A_i\)和\(B_i\)拉通，从大到小排序，考虑从最中间开始，贪心的放\(0\)/\(1\)，那么一定是一直向左放\(0\)直到达到数量上限，然后向右放，一直向右放\(1\)直到达到数量上限，然后向左放

向左放\(0\)/\(1\)时，其对应的代价就是\(2A_i/2B_i\times\)目前左边的\(1\)/\(0\)的数量；向右放同理

复杂度\(O(NlogN)\)

#include<bits/stdc++.h>
#define ll long long
#define plb pair<ll,bool>
#define fi first
#define se second
using namespace std;
const int N=305;
int n,m,cnt,l0,l1,r0,r1;
ll a[N],b[N],suma,sumb,ans;
plb c[N<<1];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%lld",&a[i]),suma+=a[i];
	for(int i=1;i<=m;++i) scanf("%lld",&b[i]),sumb+=b[i];
	sort(a+1,a+n+1),sort(b+1,b+m+1);
	if(n&1) ans+=sumb; if(m&1) ans+=suma;
	for(int i=1;i<=(n>>1)<<1;++i) c[++cnt]={a[i]<<1,0};
	for(int i=1;i<=(m>>1)<<1;++i) c[++cnt]={b[i]<<1,1};
	sort(c+1,c+cnt+1),reverse(c+1,c+cnt+1);
	for(int i=1;i<=cnt;++i){
		if(c[i].se){
			if(r1<m>>1) ++r1,ans+=c[i].fi*r0;
			else ++l1,ans+=c[i].fi*l0;
		}else{
			if(l0<n>>1) ++l0,ans+=c[i].fi*l1;
			else ++r0,ans+=c[i].fi*r1; 
		}
	}
	printf("%lld\n",ans);
	return 0;
}