桂林 ccpc D. Assumption is All You Need

题解：

因为只能前面大的和小的换，只要换的时候把大的数都往前放，例如 8  6  9  3 1 要把8换到1的位置，不能直接换，要先8,6交换；8 ，3交换；最后8,1交换；变成 6 3 9 1 8 ；这样6 3 1这3个比8小的数的相对位置就没变，对接下来的操作就没有影响；

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 3000;
int a[N], b[N], pos[N] , maxx[3000];
struct node {
int x, y;
};
vector<node>ans;
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
ans.clear();
cin >> n;
for (int i =1; i <= n; i++)
{
scanf("%d", &a[i]);
pos[a[i]] = i;
}
for (int i = 1; i <= n; i++)
{
scanf("%d", &b[i]);
}
int key = -1;
for (int i = n; i >= 1; i--)
{
if (a[i] < b[i])
{
memset(maxx, 0, sizeof maxx);//存放区间内能操作的最大值的位置
maxx[i] = i;
int p = pos[b[i]];
for (int j = i - 1; j >= p; j--) //规定查找区间
{
if (a[j] < b[i])
{
if (a[j] > a[maxx[j + 1]])//更新该区间的值
maxx[j] = j;
else
maxx[j] = maxx[j + 1];
}
else
maxx[j] = maxx[j + 1];
}
//for (auto k=p;k<=i;k++)
//{
//	cout << maxx[k] << " ";
//}
//cout << endl;
node k;
while (p < i)//操作
{
k.x = p;
k.y = maxx[p + 1];
ans.push_back(k);
swap(a[p], a[k.y]);
pos[a[k.y]] = k.y;
pos[a[p]] = p;
p = maxx[p + 1];
}
}
else if (a[i] > b[i])//比b大没得换，不可能
{
key = 0;
break;
}
}
if (key == 0)
{
cout << -1 << endl;
}
else
{
cout << ans.size() << endl;
for (auto i : ans)
{
printf("%d %dn", i.x, i.y);
}
}
}
}

最后

以上就是鳗鱼板凳最近收集整理的关于桂林 ccpc D. Assumption is All You Need的全部内容，更多相关桂林内容请搜索靠谱客的其他文章。