数学联邦政治世界观
超小超大

数学(五)

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

对第一个序列交换得到递增序列,此时所有逆序对数量都来自于第二个序列,现在对某对元素{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://www.bjxsw.cc),接着再看更方便。

相关小说

柔弱女主的封神之路 连载中
柔弱女主的封神之路
向天打月亮
柔弱女主觉醒后绑定了系统,一步步在诡异世界立足,达成灵魂与身体的双重逆袭
1.6万字8个月前
恋与伤 连载中
恋与伤
D王后
玄幻+虐恋+权谋+命相系+一本坏人泛滥的小说。讲述了四个大陆之间的感情纠葛。长篇小说!在欺骗,利用,谎言,杀戮,绝情中渲染虐的爱恋。每一次相......
78.0万字8个月前
我嘞个豆啊循环 连载中
我嘞个豆啊循环
云开半雾
以后再说吧反正剧情自我感觉良好哈只是文笔不太好如果有人看可以看见意想不到的反转哈
0.9万字5个月前
惋落 连载中
惋落
曲漾儿
〈正文已完结〉世上再无林晴,只有司清在三外之境和人界的来回穿梭,司清的心被万落给捂热了。但两人并不是一个空间的人,情爱能长久吗?
7.5万字3个月前
浮金树影 连载中
浮金树影
月见夏
慢节奏小甜文。温柔江南美人X香港高傲少爷
1.9万字1个月前
共赴山海谣 连载中
共赴山海谣
姜湖骗子
江白芷穿越了,穿越到修仙界一个七岁的乞丐孤儿,开局就是孤儿,这怎么搞啊?本来想苟活着,结果被凌霄宗大长老时长寻捡到,捡到成为宗门大师姐。本以......
1.0万字7天前