2021桂林 D. Assumption is All You Need（铜牌题）

原题链接：https://codeforces.com/gym/103409/problem/D

数组开小了，导致我多试了好多次，还去看了别人的题解。最后发现我原来的做法是可以AC的，别人的基本是如果是从小的开始遍历，就每一步替换最小的可以替换的，如果是从大的开始，每步替换最大可以替换的，和我不太一样。

我是从大到小开始遍历，并不要求做完一轮swap操作后归为目标位置，而是要让操作完的位置小于等于目标位置，并且该轮swap操作中不能让更大数的位置大于其目标位置，否则之前的做法就变得无意义了。因为后面要遍历的数都是更小的，如果该轮swap操作完成，每次都满足当前位置小于等于目标位置，则最后有所有数的当前位置都小于等于目标位置。那么只能是全等于的情况才可能，这样就达到了题目要求。

#include <bits/stdc++.h>
using namespace std;
const int N = 3e3 + 5;
int t, n, a[N], b[N], aim[N], now[N], ans[N * N][2];
int main(void) {
//	freopen("in.txt", "r", stdin);
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
now[a[i]] = i;
}
for (int i = 1; i <= n; i++) {
scanf("%d", &b[i]);
aim[b[i]] = i;
}
bool ok = true;
int k = 0;
for (int i = n; i >= 1; i--) {
while (now[i] > aim[i]) {
int pos = now[i] - 1;
while (pos >= 1 && (a[pos] < i || aim[a[pos]] < now[i])) pos--;
if (pos >= 1) {
k++;
ans[k][0] = pos;
ans[k][1] = now[i];
a[now[i]] = a[pos];
now[a[pos]] = now[i];
now[i] = pos;
a[pos] = i;
}
else break;
}
if (now[i] > aim[i]) {
ok = false;
break;
}
}
for (int i = 1; i <= n; i++)
if (a[i] != b[i]) {
ok = false;
break;
}
if (!ok) puts("-1");
else {
printf("%dn", k);
for (int i = 1; i <= k; i++)
printf("%d %dn", ans[i][0], ans[i][1]);
}
}
return 0;
}

最后

以上就是火星上灯泡为你收集整理的2021桂林 D. Assumption is All You Need（铜牌题）的全部内容，希望文章能够帮你解决2021桂林 D. Assumption is All You Need（铜牌题）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。