https://cn.vjudge.net/contest/309482#problem/C
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 400005; int a[MAXN][2]; int ans; int main() { int T; scanf("%d", &T); while (T--) { int n; scanf("%d", &n); for (int i = 0; i < n; i++) { a[i][0] = a[i][1] = 0; } long long ans = 0; for (int i = 0, x, y; i < 2 * n; i++) { scanf("%d %d", &x, &y); x--; if (y >= 2) { //Y>2的全部移动到2 ans += y - 2; y = 1; } else { //Y<1的全部移动到1 ans += 1 - y; y = 0; } if (x < 0) { //X<1的全部移动到1 ans -= x; x = 0; } if (x >= n) { //X>N的全部移动到N ans += x - (n - 1); x = n - 1; } a[x][y]++; } //cout<<" : "<<ans<<endl; for (int i = 0; i < n; i++) { //每个位置固定留一个 a[i][0]--; a[i][1]--; if (1LL * a[i][0]*a[i][1] < 0) { //如果出现上下一个多的一个少的 int t = min(abs(a[i][0]), abs(a[i][1])); if (a[i][0] > 0) { a[i][0] -= t; a[i][1] += t; } else { a[i][1] -= t; a[i][0] += t; } ans += t; } //有多的就从左边移动到右边且如果缺的话也将缺的值传递给右边 ans += abs(a[i][0]); a[i + 1][0] += a[i][0]; ans += abs(a[i][1]); a[i + 1][1] += a[i][1]; } cout << ans << endl; } return 0; }