hdu1394(枚举/树状数组/线段树单点更新&区间求和)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1394
题意:给出一个循环数组,求其逆序对最少为多少;
思路:对于逆序对: 交换两个相邻数,逆序数 +1 或 -1, 交换两个不相邻数 a, b, 逆序数 += 两者间大于 a 的个数 - 两者间小于 a 的个数;
所以只要求出初始时的逆序对数,就可以推出其余情况时的逆序对数.对于求初始逆序对数,这里 n 只有 5e3,可以直接暴力 / 树状数组 / 线段树 / 归并排序;
代码:
1.直接暴力
1 #include <iostream> 2 #include <stdio.h> 3 using namespace std; 4 5 const int MAXN = 5e3 + 10; 6 int a[MAXN]; 7 8 int main(void){ 9 int n, ans = 0; 10 while(~scanf("%d", &n)){ 11 ans = 0; 12 for(int i = 0; i < n; i++){ 13 scanf("%d", &a[i]); 14 for(int j = 0; j < i; j++){ 15 if(a[j] > a[i]) ans++; 16 } 17 } 18 int cnt = ans; 19 for(int i = 0; i < n; i++){ 20 cnt += (n - a[i] - 1) - a[i]; 21 ans = min(ans, cnt); 22 } 23 printf("%d ", ans); 24 } 25 return 0; 26 }
2.树状数组
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 using namespace std; 5 6 const int MAXN = 5e3 + 10; 7 int tree[MAXN], a[MAXN], n; 8 9 int lowbit(int x){ 10 return x & (-x); 11 } 12 13 void updata(int x, int d){ 14 while(x <= n){ 15 tree[x] += d; 16 x += lowbit(x); 17 } 18 } 19 20 int sum(int x){ 21 int ans = 0; 22 while(x > 0){ 23 ans += tree[x]; 24 x -= lowbit(x); 25 } 26 return ans; 27 } 28 29 int main(void){ 30 int ans = 0; 31 while(~scanf("%d", &n)){ 32 ans = 0; 33 memset(tree, 0, sizeof(tree)); 34 for(int i = 1; i <= n; i++){ 35 scanf("%d", &a[i]); 36 updata(a[i] + 1, 1); 37 ans += i - sum(a[i] + 1);//当前是第 i 个数,减去a[i]前面(这里包括了a[i])的数就是a[i]后面的数了,即可以和a[i]组成逆序对的数的数目 38 // ans += sum(n) - sum(a[i] + 1); 39 } 40 int cnt = ans; 41 for(int i = 1; i <= n; i++){ 42 cnt += (n - a[i] - 1) - a[i]; 43 ans = min(ans, cnt); 44 } 45 printf("%d ", ans); 46 } 47 return 0; 48 }