首页 > 代码库 > hdu - 4911 - Inversion(离散化+树状数组)
hdu - 4911 - Inversion(离散化+树状数组)
题意:一个由n个非负整数组成的序列,问进行最多k次相邻交换后最少的逆序对数 (1 ≤ n ≤ 10^5, 0 ≤ k ≤ 10^9, 0 ≤ ai ≤ 10^9)。。
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4911
——>>每次只能交换相邻的两个数,每次交换,只改变这两个数的逆序,其他的数对于这两个数的逆序没有改变,所以,求出所有的逆序对,再减去k就是答案。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 100000 + 10; int n, k; int a[MAXN], b[MAXN]; long long C[MAXN]; void Init() { memset(C, 0, sizeof(C)); } void Read() { for (int i = 0; i < n; ++i) { scanf("%d", a + i); } } int Lowbit(int x) { return x & (-x); } long long Sum(int x) { long long nRet = 0; while (x > 0) { nRet += C[x]; x -= Lowbit(x); } return nRet; } void Add(int x) { while (x <= n) { C[x]++; x += Lowbit(x); } } void Solve() { int nCnt = 0; int nId = 0; long long nReverse = 0; memcpy(b, a, sizeof(a)); sort(b, b + n); nCnt = unique(b, b + n) - b; for (int i = n - 1; i >= 0; --i) { nId = lower_bound(b, b + nCnt, a[i]) - b + 1; nReverse += Sum(nId - 1); Add(nId); } if (nReverse > k) { nReverse -= k; } else { nReverse = 0; } printf("%I64d\n", nReverse); } int main() { while (scanf("%d%d", &n, &k) == 2) { Init(); Read(); Solve(); } return 0; }
hdu - 4911 - Inversion(离散化+树状数组)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。