首页 > 代码库 > HDU 1394Minimum Inversion Number（线段树）

HDU 1394Minimum Inversion Number（线段树）

2024-07-15 05:54:56   224人阅读

题目大意是说给你一个数组(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 }

 


联系
我们