首页 > 代码库 > hdu 1394 Minimum Inversion Number - 树状数组
hdu 1394 Minimum Inversion Number - 树状数组
The inversion number of a given number sequence a1, a2, ..., an is the number of pairs (ai, aj) that satisfy i < j and ai > aj.
For a given sequence of numbers a1, a2, ..., an, if we move the first m >= 0 numbers to the end of the seqence, we will obtain another sequence. There are totally n such sequences as the following:
a1, a2, ..., an-1, an (where m = 0 - the initial seqence)
a2, a3, ..., an, a1 (where m = 1)
a3, a4, ..., an, a1, a2 (where m = 2)
...
an, a1, a2, ..., an-1 (where m = n-1)
You are asked to write a program to find the minimum inversion number out of the above sequences.
Input
The input consists of a number of test cases. Each case consists of two lines:
the first line contains a positive integer n (n <= 5000);
the next line contains a permutation of the n integers from 0 to n-1.
Output
For each case, output the minimum inversion number on a single line.
Sample Input
101 3 6 9 0 8 5 7 4 2
Sample Output
16
题目大意 求循环排列最小逆序对数。
老是刷cf，不做暑假作业估计会被教练鄙视，所以还是做做暑假作业。
先用各种方法算出原始序列的逆序对数。
显然你可直接算出把开头的一个数挪到序列后面增加的逆序对数。(后面有多少个比它大减去有多少个比它小)
于是这道题就水完了。
Code
1 /** 2 * hdu 3 * Problem#1394 4 * Accepted 5 * Time: 62ms 6 * Memory: 1680k 7 */ 8 #include <iostream> 9 #include <fstream> 10 #include <sstream> 11 #include <cstdio> 12 #include <ctime> 13 #include <cmath> 14 #include <cctype> 15 #include <cstring> 16 #include <cstdlib> 17 #include <algorithm> 18 #include <map> 19 #include <set> 20 #include <list> 21 #include <stack> 22 #include <queue> 23 #include <vector> 24 #ifndef WIN32 25 #define Auto "%lld" 26 #else 27 #define Auto "%I64d" 28 #endif 29 using namespace std; 30 typedef bool boolean; 31 const signed int inf = (signed)((1u << 31) - 1); 32 const signed long long llf = (signed long long)((1ull << 61) - 1); 33 const double eps = 1e-9; 34 const int binary_limit = 256; 35 #define smin(a, b) a = min(a, b) 36 #define smax(a, b) a = max(a, b) 37 #define max3(a, b, c) max(a, max(b, c)) 38 #define min3(a, b, c) min(a, min(b, c)) 39 template<typename T> 40 inline boolean readInteger(T& u){ 41 char x; 42 int aFlag = 1; 43 while(!isdigit((x = getchar())) && x != ‘-‘ && x != -1); 44 if(x == -1) { 45 ungetc(x, stdin); 46 return false; 47 } 48 if(x == ‘-‘){ 49 x = getchar(); 50 aFlag = -1; 51 } 52 for(u = x - ‘0‘; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - ‘0‘); 53 ungetc(x, stdin); 54 u *= aFlag; 55 return true; 56 } 57 58 #define lowbit(x) ((x) & (-x)) 59 60 typedef class IndexedTree { 61 public: 62 int* lis; 63 int s; 64 IndexedTree() { } 65 IndexedTree(int s):s(s) { 66 lis = new int[(s + 1)]; 67 memset(lis, 0, sizeof(int) * (s + 1)); 68 } 69 70 inline void add(int idx, int val) { 71 for(; idx <= s; idx += lowbit(idx)) 72 lis[idx] += val; 73 } 74 75 inline int getSum(int idx) { 76 int ret = 0; 77 for(; idx; idx -= lowbit(idx)) 78 ret += lis[idx]; 79 return ret; 80 } 81 }IndexedTree; 82 83 int n; 84 int* arr; 85 inline boolean init() { 86 if(!readInteger(n)) return false; 87 arr = new int[(n + 1)]; 88 for(int i = 1; i <= n; i++) 89 readInteger(arr[i]), arr[i] += 1; 90 return true; 91 } 92 93 IndexedTree it; 94 int ans, cmp; 95 inline void solve() { 96 ans = 10000000, cmp = 0; 97 it = IndexedTree(n); 98 for(int i = 1; i <= n; i++) { 99 it.add(arr[i], 1);100 // cout << 1;101 cmp += i - it.getSum(arr[i]);102 }103 ans = cmp;104 for(int i = 1; i < n; i++) {105 cmp -= arr[i] - 1, cmp += n - arr[i];106 smin(ans, cmp);107 }108 printf("%d\n", ans);109 }110 111 inline void clear() {112 delete[] arr;113 delete[] it.lis;114 }115 116 int main() {117 while(init()) {118 solve();119 clear();120 }121 return 0;122 }
hdu 1394 Minimum Inversion Number - 树状数组