题解
逆序对数最小的排列是严格升序的排列,因此我猜想有一个严格升序的排列最优的
证明;
冒泡排序,我们把排列a中最大的元素不断地往右作相邻对换,这样一来,序列a的逆序对数必定减少一,序列b的逆序对数可能减少一,可能不变,可能加一,但是两个排列的总逆序对数不可能增加。
然后再逆着想验证了这种策略的可行性
codee
#include<bits/stdc++.h>
using namespace std;
struct unit
{
int x,y;
}a[200005];
bool cmp(unit x,unit y)
{
return x.x<y.x;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i].x;
for(int i=1;i<=n;i++) cin>>a[i].y;
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++) cout<<a[i].x<<" ";
puts("");
for(int i=1;i<=n;i++) cout<<a[i].y<<" ";
puts("");
}
return 0;
}
标签:排列,Minimize,int,升序,Inversions,对数,unit,逆序
From: https://www.cnblogs.com/pure4knowledge/p/18040737