利用归并排序求数组中逆序对的数量洛谷p1908
2022/4/3 23:22:35
本文主要是介绍利用归并排序求数组中逆序对的数量洛谷p1908,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
import java.io.InputStreamReader;
import java.util.Scanner;
public class Main {
static long result=0;
public static void merge_sort(int q[],int l,int r) {
if(l>=r) {
return;
}
int mid=l+r>>1;
int k=0;int[] temp=new int[r-l+1];
int i=l;int j=mid+1;
merge_sort(q,l,mid);
merge_sort(q,mid+1,r);
while(i<=mid&&j<=r) {
if(q[i]<=q[j]) {
temp[k++]=q[i++];
}
else {
temp[k++]=q[j++];
result+=mid-i+1;
}
}
while(i<=mid) {
temp[k++]=q[i++];
}
while(j<=r) {
temp[k++]=q[j++];
}
for(int w=l,e=0;w<=r;w++,e++) {
q[w]=temp[e];
}
}
public static void main(String[] args) {
Scanner scan=new Scanner(new InputStreamReader(System.in));
int n=scan.nextInt();
int[] arr=new int [n];
for(int i=0;i<n;i++) {
arr[i]=scan.nextInt();
}
merge_sort(arr,0,n-1);
System.out.print(result);
scan.close();
}
}
这篇关于利用归并排序求数组中逆序对的数量洛谷p1908的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?