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

数学(五)

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

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

相关小说

路西法今天堕天了吗? 连载中
路西法今天堕天了吗?
加木男
上帝不容亵渎,拥护他的前行。
3.4万字8个月前
你惹她?疯癫大佬她最爱斩鬼灭神 连载中
你惹她?疯癫大佬她最爱斩鬼灭神
我饼画的圆
神商止刚睁开眼,就被恶鬼死死掐住脖子开局真凶险,她反手就是一耳光想让老娘现在就挂?打的就是你!面对这颠婆,资深红衣鬼只能跪坐在地哭卿卿——为......
67.2万字7个月前
梦回山海 连载中
梦回山海
要献便献吻_37211257035372
本是青梅竹马,却了天意弄人。梦回过去。你还会做出同样的选择?
3.1万字6个月前
紫色荆棘之光影 连载中
紫色荆棘之光影
朦零空悦
神秘人的出现为什么让凤聆蝶警戒,神秘人的出现又代表着什么?神秘人的姐姐到底能不能压制她,结局又会是怎样的?
2.7万字3个月前
穿越神印之无敌 连载中
穿越神印之无敌
吟风由
女主无敌,无脑强,微恶女,什么都以自己为先
0.9万字2个月前
山茶随笔 连载中
山茶随笔
山茶与月
一些美好的幻想
7.0万字4周前