逆序数 HDOJ 4911 Inversion
2024-08-30 15:22:17
题意:可以交换两个相邻的数字顺序k次,问最后逆序对最少有多少
分析:根据逆序数的定理如果逆序数大于0,那么必定存在1<=i<n使得i和i+1交换后逆序数减1假设原逆序数为cnt,这样的话,我们就可以得到答案是max(cnt-k,0)求逆序数可以用归并的方法
代码:
/************************************************
* Author :Running_Time
* Created Time :2015/9/12 星期六 20:31:07
* File Name :J.cpp
************************************************/ #include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
int a[N], L[N/2], R[N/2];
ll cnt; void Merge(int *a, int p, int q, int r) {
int n1 = q - p + 1, n2 = r - q;
for (int i=1; i<=n1; ++i) L[i] = a[p+i-1];
for (int i=1; i<=n2; ++i) R[i] = a[q+i];
L[n1+1] = R[n2+1] = INF;
for (int i=1, j=1, k=p; k<=r; ++k) {
if (L[i] <= R[j]) a[k] = L[i++];
else {
a[k] = R[j++]; cnt += n1 - i + 1;
}
}
} void Merge_Sort(int *a, int p, int r) {
if (p < r) {
int q = (p + r) >> 1;
Merge_Sort (a, p, q);
Merge_Sort (a, q+1, r);
Merge (a, p, q, r);
}
} int main(void) {
int n; ll k;
while (scanf ("%d%I64d", &n, &k) == 2) {
for (int i=1; i<=n; ++i) scanf ("%d", &a[i]);
cnt = 0;
Merge_Sort (a, 1, n);
printf ("%I64d\n", max (cnt - k, (ll) 0));
} return 0;
}
最新文章
- Eclipse利用Maven2搭建SpringMVC框架的Web工程
- iOS单例模式(Singleton)写法简析
- CentOS 6.4下安装Oracle 11gR2
- js获取页面url的方法
- ExtJS学习之路第八步:Window组件
- [Ubuntu] Ubuntu14.04 64bit 编译安装nginx1.7+php5.4+mysql5.6
- c++学习-链表
- 上传至应用商店以及testflight相关。
- 包装 request Demo
- Python学习笔记【第十一篇】:Python面向对象高级
- Hdoj 2109.Fighting for HDU 题解
- linux下socket的连接队列的 backlog的分析
- Python上下文管理器 with
- 【转】CSR蓝牙驱动程序引起的Win7奇怪问题
- jquery mobile两个页面以及源码(登录与注册) 转
- docker使用非root用户启动容器出现“running exec setns process for init caused \";exit status 40\";";: unknown”
- 获取web页面xpath
- 关于有些邮件可以在http上发送成功但是https不能发送成功一个思路方法
- java基础----->;TCP和UDP套接字编程
- python字典格式化输出