1 条题解
-
0
以下称 到 在同一个块, 到 在同一个块,两个块不一样。
对于一次临项交换只有两种情况要么在同一个块,要么在两个块的交界处。
不难得出只要在一个块内有 ,那么逆序对就能变为任意值。
接下来考虑在两个块的交界处。
只会呈现两种形态 状和 状。 ::::info[ 状分析] 对于左边的块:交换之后 在最后就没有什么作用了,设 到 都是 ,交换之后左边块内的逆序对数为 到 的逆序对数。
对于右边的块:交换之后 就堆在最左边了,也没什么用,设 到 都是 ,交换之后右边块内的逆序对数为 到 的逆序对数。 :::: ::::info[ 状分析] 对于左边的块:设交换之后 到 都是 ,那么逆序对数为 到 的逆序对数加上 。
对于右边的块:设交换之后 到 都是 ,那么逆序对数为 到 的逆序对数加上 $[r - (n + 1) + 1] \times \sum^{2 \times n}_{i = r + 1} (1 - a_i)$。 :::: 由于进行一次 状操作后再进行 状操作等于没进行操作,显然无用,所以可以枚举两种操作的使用次数,然后再取最小值。
#include<bits/stdc++.h> const int MAXN = 2e5 + 5; #define pb push_back typedef long long LL; const LL inf = 1e15; int n, a[2 * MAXN]; std::vector<int> v[2][2]; LL suf[MAXN][2], pre[MAXN][2]; inline void init() { for(int i = n; i >= 1; i--) { v[0][a[i]].pb(i); } for(int i = n + 1; i <= 2 * n; i++) { v[1][a[i]].pb(i); } int c = 0, c1 = 0, c2 = 0; for(int i = 1; i <= n; i++) { if(a[i] == 1) c1++; else c += c1; suf[i][0] = c; } c = c1 = c2 = 0; for(int i = 2 * n; i >= n + 1; i--) { if(a[i] == 0) c2++; else c += c2; suf[i][1] = c; } c = 0; for(int i = 1; i <= n; i++) { if(a[i] == 1) c++; pre[i][0] = c; } c = 0; for(int i = 2 * n; i >= n + 1; i--) { if(!a[i]) c++; pre[i][1] = c; } } int main() { scanf("%d", &n); for(int i = 1; i <= 2 * n; i++) { scanf("%d", &a[i]); } init(); LL ans = abs(suf[n][0] - suf[n + 1][1]), s = 0; for(int i = 0; i < std::min(v[0][0].size(), v[1][1].size()); i++) { int l = v[0][0][i], r = v[1][1][i]; LL nl = suf[l - 1][0], nr = suf[r + 1][1]; s += (n - l) + (r - (n + 1)) + 1; ans = std::min(ans, s + abs(nl - nr)); } init(); s = 0; for(int i = 0; i < std::min(v[0][1].size(), v[1][0].size()); i++) { int l = v[0][1][i], r = v[1][0][i]; LL nl = suf[l - 1][0] + 1LL * (n - l + 1) * pre[l - 1][0], nr = suf[r + 1][1] + 1LL * (r - (n + 1) + 1) * pre[r + 1][1]; s += (n - l) + (r - (n + 1)) + 1; ans = std::min(ans, s + abs(nl - nr)); } printf("%lld\n", ans); return 0; }
- 1
信息
- ID
- 6947
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- 递交数
- 36
- 已通过
- 7
- 上传者