目录
涵涵有两盒火柴,每盒装有 n 根火柴,每根火柴都有一个高度。
现在将每盒中的火柴各自排成一列,同一列火柴的高度互不相同,两列火柴之间的距离定义为:
其中 ai 表示第一列火柴中第 i 个火柴的高度,bi 表示第二列火柴中第 i 个火柴的高度。
每列火柴中相邻两根火柴的位置都可以交换,请你通过交换使得两列火柴之间的距离最小。
请问得到这个最小的距离,最少需要交换多少次?
如果这个数字太大,请输出这个最小交换次数对 99,999,997 取模的结果。
输入格式
共三行,第一行包含一个整数 n,表示每盒中火柴的数目。
第二行有 n 个整数,每两个整数之间用一个空格隔开,表示第一列火柴的高度。
第三行有 n 个整数,每两个整数之间用一个空格隔开,表示第二列火柴的高度。
输出格式
输出共一行,包含一个整数,表示最少交换次数对 99,999,997 取模的结果。
数据范围
1≤n≤10^5,
0≤火柴高度≤2^31−1,
输入样例:
- 4
- 2 3 1 4
- 3 2 1 4
输出样例:
1
离散化+归并排序求逆序对(或者树状数组求逆序对)
树状数组比较抽象,这里以归并排序为例。先听我阐述一下大体思路,后面细节听我娓娓道来。这个题一看无非是交换序列最小次数,如果我们固定第一组数据,那么第二组数据就按照第一组的数据大小排列即可保证最小距离,那么我们把第一组数据排一下序,第二组的数据是不是就好处理了。由于数据量很大,且数据不集中很离散,可能会爆栈,考虑离散化。那么我们把数组a,b都处理好了下面考虑移动几次就好了。根据结论,一个数组b中的元素移动到另一个数组a使其位置相同,最少需要移动b的逆序对数(前提是排好序),那么我们如何求逆序对呢,想一想归并排序的实现,可以利用前面数组l的数l[i]大于后面数组r的数r[j]的特点,若前面数组l的数l[i]大于后面数组r的数r[j],说明数组l此时位置i往后到mid的位置都是逆序对数,因为数组l是有序的,既然此时的位置i都要大于数组r的数r[j],那么l[i]到l[mid]都是大于r[j]的,那么逆序对数就是mid-i+1,总的逆序对数即为答案。
离散化,把无限空间中有限的个体映射到有限的空间中去,以此提高算法的时空效率。
通俗的说,离散化是在不改变数据相对大小的条件下,对数据进行相应的缩小。例如:
原数据:1,999,100000,15;处理后:1,3,4,2;
什么时候使用离散化,当数据很离散且很大,当要去此值当作数组下标,例如n<=1e5;0<=a[i]<=1e9。
下面写一个模板
- #include
- #include
- using namespace std;
- const int N=1e5+5;
- const int M=1e9+5;
- int a[N];
- int n;
- int main(){
- cin>>n;
- for(int i=1;i<=n;i++){
- cin>>a[i];
- }
- sort(a+1,a+n+1);//排序
- int len=unique(a+1,a+n+1)-(a+1);//去重,len为新长度
- for(int i=1;i<=len;i++){
- cout<" ";//排序好的数据
- a[i]=lower_bound(a+1,a+n+1,a[i])-a;
- cout<//离散化映射下标
- }
- return 0;
- }
下面写一下求逆序对函数:
- int merge_sort(int l,int r){
- if(l>=r)return 0;
- int mid=l+r>>1;
- int res=(merge_sort(l,mid)+merge_sort(mid+1,r))%mod;
- int i=l,j=mid+1,k=0;
- while(i<=mid&&j<=r){
- if(b[i]<=b[j])p[k++]=b[i++];
- else p[k++]=b[j++],res=(res+mid-i+1)%mod;
- }//只有前面数组大于后面数组的数时,才满足逆序对
- while(i<=mid)p[k++]=b[i++];
- while(j<=r)p[k++]=b[j++];
- for(int i=l,j=0;i<=r;i++,j++)b[i]=p[j];
- return res;
- }
- #include
- #include
- using namespace std;
- const int mod=99999997;
- const int N=1e5+5;
- int n;
- int a[N],b[N],c[N],p[N];
- int find(int x){//二分查找
- int l=1,r=n;
- while(l
- int mid=l+r>>1;
- if(p[mid]>=x)r=mid;
- else l=mid+1;
- }
- return l;
- }
- void work(int a[]){//离散化函数
- for(int i=1;i<=n;i++)p[i]=a[i];
- sort(p+1,p+n+1);
- for(int i=1;i<=n;i++){
- a[i]=find(a[i]);
- //a[i]=lower_bound(p+1,p+n+1,a[i])-p;可以用lower_bound函数更简单
- }
- return;
- }
- int merge_sort(int l,int r){//归并求逆序对
- if(l>=r)return 0;
- int mid=l+r>>1;
- int res=(merge_sort(l,mid)+merge_sort(mid+1,r))%mod;
- int i=l,j=mid+1,k=0;
- while(i<=mid&&j<=r){
- if(b[i]<=b[j])p[k++]=b[i++];
- else p[k++]=b[j++],res=(res+mid-i+1)%mod;
- }
- while(i<=mid)p[k++]=b[i++];
- while(j<=r)p[k++]=b[j++];
- for(int i=l,j=0;i<=r;i++,j++)b[i]=p[j];
- return res;
- }
- int main(){
- cin>>n;
- for(int i=1;i<=n;i++)cin>>a[i];
- for(int i=1;i<=n;i++)cin>>b[i];
- work(a),work(b);
- for(int i=1;i<=n;i++)c[a[i]]=i;
- for(int i=1;i<=n;i++)b[i]=c[b[i]];
- cout<<merge_sort(1,n)<
- return 0;
- }
此题比较抽象,需要很多转化处理,可以看一看B站的讲解,笔者写可能有不准确的地方,一些地方也不是最优解法,望大家理解,若有错误请大家指出共同进步。
-
相关阅读:
获取Windows 10中的照片(旧版)下载
V8 GC 的实现
Chant 开发人员工作台2022支持转录和单词定位
中国平安接近触底
你还只知道测试金字塔?
CodeForces - 667A Pouring Rain
推荐算法学习笔记2.1:基于深度学习的推荐算法-基于共线矩阵的深度推荐算法-NeuralCF模型
实验2 存储器设计与实现【计算机组成原理】
使用Python进行页面开发——CSS
1-EleasticSearch高可用集群核心原理
-
原文地址:https://blog.csdn.net/m0_73633807/article/details/136558538