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

数学(五)

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

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

相关小说

作者的发疯或随笔 连载中
作者的发疯或随笔
季亭.
作者的发疯随笔小日常而已啦,可能存在多元素,毕竟我有的时候可能就灵感爆发,嗯,想写一些如咒回文野的同人短文我可能就会写在这里,当然更多时候是......
0.5万字6个月前
日常做梦指南 连载中
日常做梦指南
庄馨
许多个小短篇故事,轻松随意,建议睡前食用摘选:一.我知道源哥搞音乐的是艺术家,搞艺术的呢就会经常感性,经常忧郁,不过当初的我只觉得,他那么阳......
0.5万字5个月前
无限流BOSS是我的第二人格 连载中
无限流BOSS是我的第二人格
雪意落誓烬
  【记忆是一个不可描述的东西,你真的没有失忆吗?】  很平常的一天,宋时堇的体内突然多了一个来自千年前的灵魂,那人自称是他前世的爱人,后来......
3.8万字3个月前
棋中谋心 连载中
棋中谋心
吗喽啰
0.9万字2个月前
错付之我发现了他的白月光 连载中
错付之我发现了他的白月光
花影哩
女主和男主结婚3年后,女主发现了他的白月光,才明白这三年他终究是错付了……
0.4万字1个月前
禁止偶像恋爱条例 连载中
禁止偶像恋爱条例
傅了个钰
「在聚光灯照不到的地方,我遇见了最真实的你。」颜书,摄影系普通大学生,因一次偶然的机会成为顶流男团**TNT时代少年团**的临时摄影师。镜头......
2.2万字4天前