数学（五）

思路：先把第一个序列排序，第二个序列的顺序不定。

对第一个序列交换得到递增序列，此时所有逆序对数量都来自于第二个序列，现在对某对元素{i，j}操作，使其顺序改变后，第一个序列一定会增加k个逆序对，但是第二个序列减少逆序对一定＜=k，得不偿失了，所以只需要对一个序列排序即可。

证明：为简化运算，我们将排序移动过程全部变为相邻项交换。

当第一个序列为严格递增序列时，第二个序列想要减少逆序对数量时，每项不在原有位置上的元素都要移动相应距离，在移动过程中每与相邻项交换一次，第一个序列逆序对一定减1，但是第二个逆序对数量最多减少1。

举个例子：

第二个序列为3 4 1 2，想要元素3回到它应在的位置上，需要交换两次，当元素3，4交换时，逆序对数量不减反增，第一个序列逆序对加1，以此类推。

#include＜iostream＞

#include＜cstring＞

#include＜vector＞

using namespace std;

using LL = long long;

int main(){

cin.tie(0);

cout.tie(0);

ios::sync_with_stdio(0);

int T;

cin＞＞T;

while(T--){

int n;

cin＞＞n;

vector＜int＞ a(n), b(n);

for(int i = 0; i＜n; i++) cin＞＞a[i];

for(int i = 0; i＜n; i++) cin＞＞b[i];

vector＜int＞ id(n);

for(int i = 0; i＜n; i++) id[i] = i;

sort(id.begin(), id.end(), [&](int x, int y){

return a[x]＜a[y];

});

for(int i = 0; i < n; i++){

cout ＜＜ a[id[i]] ＜＜ ' ';

}

cout ＜＜ '\n';

for(int i = 0; i < n; i++){

cout ＜＜ b[id[i]] ＜＜ ' ';

}

cout ＜＜ '\n';

}

}

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。