[ARC120C] Swaps 2
\(-1\) 的情况判错卡了 \(10\) 几分钟，麻了。
题面翻译
给出 \(2\) 个序列 \(a\) 和 \(b\)，定义一次操作为：
- 选定一个下标 \(i\)，先将 \(a_i\) 以及 \(a_{i+1}\) 交换，然后让 \(a_i\) 加一，最后让 \(a_{i+1}\) 减一。
求最少操作次数使得 \(a\) 序列等于 \(b\) 序列，否则输出 -1。
Solution
手动模拟几次操作之后，发现：
\(a_i\) 经过一次操作后变成的 \(a_{i+1}+i+1\) 不会变。
举个栗子：\(a_1 = 4\)，\(a_2 = 6\)，对 \(a_1\) 进行操作，\(a_1 = 7\)，\(a_2 = 3\)，\(1+4 = 2+3\)。
由于结论显然，这里不作证明了。
于是问题便转化为了：
给出 \(2\) 个序列 \(a\) 和 \(b\)，每次操作你可以交换 \(a\) 中相邻的 \(2\) 个数，求使 \(a\) 等于 \(b\) 的最小操作次数。
这是个小 \(trick\)，该问题可转化为求逆序对个数，这里使用归并排序求逆序对数，时间复杂度为 \(O(n \times \log_{2}{n})\)。
至于判断负数，有 \(2\) 种情况：
-
两个序列总和不同。（因为操作不影响序列的总和）
-
转化过后的 \(a\) 序列和 \(b\) 序列有不同数字。
其实第 \(1\) 种情况本质上就是第 \(2\) 种情况。
至于如何处理，将 \(a\) 中数字放入 map 中计数，再在 \(b\) 中判断即可。
代码
// written by Naught
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define Maxn 200005
#define fo(i, l, r) for (int i = l; i <= r; ++i)
#define fr(i, r, l) for (int i = l; i >= r; --i)
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21], *p1 = buf, *p2 = buf;
inline int read(int x=0, bool f=0, char c=getchar()) {for(;!isdigit(c);c=getchar()) f^=!(c^45);for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);return f?-x:x;}
int n, sum_cnt, a[Maxn], b[Maxn], A[Maxn], B[Maxn], c[Maxn];
ll sum, ans;
map<int, queue<int>> mp;
map<int, int> cnt;
void merge_sort(int l, int r)
{
if ( l == r ) return;
int mid = (l + r) >> 1, i = l, j = mid+1, k = l;
merge_sort( l , mid );
merge_sort( mid+1 , r );
while ( i <= mid && j <= r )
if(a[i] <= a[j]) c[k++] = a[i++];
else c[k++] = a[j++], ans += mid-i+1;
while ( i <= mid ) c[k++] = a[i++];
while ( j <= r ) c[k++] = a[j++];
fo(i, l, r) a[i] = c[i];
}
signed main()
{
n = read();
fo(i, 1, n) a[i] = read(), A[i] = a[i]+i, sum += a[i], ++cnt[A[i]], sum_cnt += cnt[A[i]] == 1;
fo(i, 1, n) b[i] = read(), B[i] = b[i]+i, mp[B[i]].push(i), sum -= b[i], --cnt[B[i]], sum_cnt -= cnt[B[i]] == 0;
if(sum_cnt || sum) return puts("-1"), 0;
fo(i, 1, n) a[i] = mp[A[i]].front(), mp[A[i]].pop();
merge_sort(1, n);
printf("%lld", ans);
return 0;
}