【Incubator DAY18】Interesting exchange【Simulation】【Math】

思路：

我们发现只有当n和n+1To turn over,We don't know what to do.
那么我们考虑,If the first half turned a1过去,During the second half turned a0过去,Then reverse the number can be calculated.
Then we will direct enumeration first half turned a few1过去,Then calculate the answer again and again.

$code$

#include<iostream>
#include<cstdio>
#include<cmath>

#define ll long long

using namespace std;

const ll MAXN = 1e5 + 10;

ll n, x1[MAXN], y_1[MAXN], x0[MAXN], y_0[MAXN];
ll l1, l0, r1, r0, ans;

int main() {
    
	freopen("balance.in", "r", stdin);
	freopen("balance.out", "w", stdout);
	scanf("%lld", &n);
	for(ll i = 1; i <= n; i ++) {
    
		ll x;
		scanf("%lld", &x);
		if(x == 1) x1[++ l1] = i;
		else x0[++ l0] = i;
	}
	for(ll i = 1; i <= n; i ++) {
    
		ll x;
		scanf("%lld", &x);
		if(x == 1) y_1[++ r1] = i;
		else y_0[++ r0] = i;
	}
	ll suml = (n - l1) * l1 + (l1 + 1) * l1 / 2, sumr = (n - r1) * r1 + (r1 + 1) * r1 / 2;
	for(ll i = 1; i <= l1; i ++) suml -= x1[i];
	for(ll i = 1; i <= r1; i ++) sumr -= y_1[i];
	if(suml == sumr) {
    
		printf("0");
		return 0;
	}
	ans = abs(suml - sumr);
	ll sl = suml, sr = sumr;
	ll tmp = 0;
	for(ll i = l1, j = 1; i >= 1 && j <= r0; i --, j ++) {
    
		sl += x1[i] - n + i - 1;
		sr += r0 - j - y_0[j] + 1;
		tmp += n - x1[i] + y_0[j];
		if(tmp >= ans) break;
		ans = min(ans, tmp + (sl - sr < 0 ? sr - sl : sl - sr));
	}
	sl = suml, sr = sumr;
	tmp = 0;
	for(ll i = l0, j = 1; i >= 1 && j <= r1; i --, j ++) {
    
		sr += y_1[j] - n + r1 - j;
		sl += i - x0[i];
		tmp += n - x0[i] + y_1[j];
		if(tmp >= ans) break;
		ans = min(ans, tmp + (sl - sr < 0 ? sr - sl : sl - sr));
	}
	printf("%lld", ans);
	return 0;
}