【hiho39】二分·归并排序之逆序对
2024-08-28 23:13:17
近期申请了微软的暑假实习,4号就要在线笔试了,在线測试系统用的是http://hihocoder.com/,今天试手做了一道题。
【题目】
原题链接:http://hihocoder.com/contest/hiho39/problem/1
输入
第1行:1个整数N,表示数组长度。
第2行:N个整数,表示数组的元素a[i],1≤a[i]≤2^31-1。
输出
第1行:1个整数,表示有多少对元素满足a[i]>a[j],i<j。
例子输入
10
1559614248 709366232 500801802 128741032 1669935692 1993231896 369000208 381379206 962247088 237855491
例子输出
27
【Java代码】
import java.util.Scanner;
import java.math.BigInteger; public class Main {
//public int ans = 0;
public BigInteger ans = BigInteger.ZERO; public void mergeSort(int[] a, int l, int r) {
if (l >= r) return;
int mid = (l + r) >> 1;
mergeSort(a, l, mid);
mergeSort(a, mid + 1, r);
merge(a, l, mid, r);
} public void merge(int[] a, int l, int mid, int r) {
int[] b = new int[r - l + 1];
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) {
b[k++] = a[i++];
} else {
//ans += mid - i + 1;
ans = ans.add(new BigInteger(String.valueOf(mid - i + 1)));
b[k++] = a[j++];
}
}
while (i <= mid) {
b[k++] = a[i++];
}
while (j <= r) {
b[k++] = a[j++];
}
i = l;
j = 0;
while (i <= r) {
a[i++] = b[j++];
}
} public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int[] a = new int[N];
for (int i = 0; i < N; i++) {
a[i] = in.nextInt();
} Main m = new Main();
m.mergeSort(a, 0, N - 1); //System.out.println(m.ans);
System.out.println(m.ans.toString());
}
}
代码中凝视部分是第一次提交的代码,得分为80/100。看讨论得知是int会溢出,所以换成BigInteger。
Tips:像这样的部分test case通只是时,就要考虑大数溢出的情况。
最新文章
- 如何在ashx页面获取Session值
- overflow:hidden清楚浮动的影响
- WPF功能点
- Codeforces Round #379 (Div. 2) D. Anton and Chess 水题
- SwipeRefreshLayout下拉刷新
- js比typeof更准确的验证类型方法
- Ugly Window 【acm题】
- 【转】15 个用于 GitHub 的 Chrome 插件
- 编写3个不同版本的程序,令其均能输出ia的元素
- pythom 安装MySQL-pythom的问题
- HTTP学习实验8-windows添加telnet功能
- css3毛玻璃模糊效果
- 以Windows服务方式运行.NET Core程序
- python windows 下pip easy_install 使用错误的问题
- P1616疯狂的采药
- kafka config
- 前端基础之css介绍
- js中Math.round、parseInt、Math.floor和Math.ceil小数取整小结
- AGC006C Rabbit Exercise
- vim中将tab 设置成4个空格