首页 > 代码库 > HDU 1394Minimum Inversion Number(线段树)
HDU 1394Minimum Inversion Number(线段树)
题目大意是说给你一个数组(N个),没戏可以将其首部的k(k<N)个元素移动至尾部,这样总共会形成N个序列
现在要求这n个序列中逆序对数最少的那一个序列有多少个逆序对
最初的确是没太多思路,就算知道线段书可以球某一个序列的逆序对数,但是这里要求n次,就没有太多把握了
而最后的方法其实的确是只用求一次的,由于给出的n个数字是0~n-1的一个排列,所以考虑吧a[0]放到最后一个位置时,那以它作为起点的逆序对数相应的会减少a[0]个(这是因为塔处在地一个位置,所有比它晓得数都会在其后方), 然后考虑a[0]已经被移动到最后一个位置,那么相应的这个序列的逆序对数会增加n-a[0]个
所以只要在一遍线段书或树状数组求出开始时的逆序对数后,后面的可以由它递推得到
1 #include <map> 2 #include <set> 3 #include <stack> 4 #include <queue> 5 #include <cmath> 6 #include <ctime> 7 #include <vector> 8 #include <cstdio> 9 #include <cctype>10 #include <cstring>11 #include <cstdlib>12 #include <iostream>13 #include <algorithm>14 using namespace std;15 #define INF 1e916 #define inf (-((LL)1<<40))17 #define lson k<<1, L, mid18 #define rson k<<1|1, mid+1, R19 #define mem0(a) memset(a,0,sizeof(a))20 #define mem1(a) memset(a,-1,sizeof(a))21 #define mem(a, b) memset(a, b, sizeof(a))22 #define FOPENIN(IN) freopen(IN, "r", stdin)23 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)24 template<class T> T CMP_MIN(T a, T b) { return a < b; }25 template<class T> T CMP_MAX(T a, T b) { return a > b; }26 template<class T> T MAX(T a, T b) { return a > b ? a : b; }27 template<class T> T MIN(T a, T b) { return a < b ? a : b; }28 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }29 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b; }30 31 typedef __int64 LL;32 //typedef long long LL;33 const int MAXN = 5005;34 const int MAXM = 100005;35 const double eps = 1e-10;36 const LL MOD = 1000000007;37 38 int c[MAXN], a[MAXN], id[MAXN], N;39 40 int lowbit(int x)41 {42 return x & (-x);43 }44 45 void update(int k, int x)46 {47 while(k <= N)48 {49 c[k] += x;50 k += lowbit(k);51 }52 }53 54 int getSum(int k)55 {56 int sum = 0;57 while(k > 0)58 {59 sum += c[k];60 k -= lowbit(k);61 }62 return sum;63 }64 65 int cmp(int i, int j)66 {67 return a[i] > a[j];68 }69 70 int getCnt()71 {72 for(int i=1;i<=N;i++) id[i] = i;73 sort(id+1, id + N + 1, cmp);74 mem0(c);75 int cnt = 0;76 for(int i=1;i<=N;i++)77 {78 cnt += getSum(id[i]);79 update(id[i], 1);80 }81 return cnt;82 }83 84 int main()85 {86 while(scanf("%d", &N) == 1)87 {88 for(int i=1;i<=N;i++) scanf("%d", &a[i]);89 int ans = getCnt(), x = ans;90 for(int i=1;i<N;i++)91 {92 x = x + N - 2 * a[i] - 1;93 ans = MIN(ans, x);94 }95 printf("%d\n", ans);96 }97 return 0;98 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。