首页 > 代码库 > hdu--4911--归并排序||树状数组
hdu--4911--归并排序||树状数组
发现一个小小的 逆序数里真的藏了好多东西啊=-=
解决这题 你需要知道一点...
对于一串给定的数字 我随便写一串吧..
index: 0 1 2 3 4
value: 4 8 7 5 6 这时候 总的逆序对数是 3+2=5 假如我们只能进行相邻元素的交换 这最好情况是什么呢？
那肯定就是假如本来 arr[x]>arr[x+1] 那这样是形成一个逆序数的吧 我们将它进行交换 这样就少了一个逆序数对是吧...
但是 对于其它位置的元素是没有影响的对吧
所以 我们需要的最小次数呢 就是sum<即原数组的逆序数个数> 然后把它和k比较下大小就是了
看到了disucss里面的帖子 才第一次 知道 sort是不稳定的排序...这题里要用stable_sort。。没用树状数组去写-呆会写
每天mhxy 和lol 玩来玩去 超累啊=-=
1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 5 typedef long long LL; 6 LL sum; 7 const int size = 100010; 8 int arr[size]; 9 int temp[size];10 11 void merge_sort( int l , int r )12 {13 int mid , p , q , i;14 if( r-l > 1 )15 {16 mid = l + (r-l) / 2;17 p = l;18 q = mid;19 i = l;20 merge_sort( l , mid );21 merge_sort( mid , r );22 while( p<mid || q<r )23 {24 if( q>=r || (p<mid && arr[p] <= arr[q] ) )25 {26 temp[i++] = arr[p++];27 }28 else29 {30 temp[i++] = arr[q++];31 sum += (mid-p);32 }33 }34 for( i = l ; i<r ; i++ )35 {36 arr[i] = temp[i];37 }38 }39 }40 41 int main()42 {43 cin.sync_with_stdio(false);44 int n;45 LL k;46 while( cin >> n >> k )47 {48 sum = 0;49 for( int i = 0 ; i<n ; i++ )50 {51 cin >> arr[i];52 }53 merge_sort( 0 , n );54 cout << max( sum-k , (LL)0 ) << endl;55 }56 return 0;57 }
这边要注意下 0的前面要用LL进行强制转换 不然会CE..因为前者是LL类型的..
做逆序数对的时候 很容易会是用到64位的 因为 假如给你这么组BT数组 X , X-1 , X-2 , X-3 , …………x-i,x-i-1,…………,1 那就是Ah 等差数列求和#24.。
这边留一大片空白 给待会写的 树状数组....
突然 想再写点关于刚刚的归并排序的一些东西<因为我觉得归并很难啊 我最烦这种递归的了 卧槽..真羡慕那些写递归和写for一样的人..#80>
似乎 归并排序的 分治操作将它不断进行二分的操作 最终在分成只有一个元素的时候 结束了递归
然后开始一步步从结束递归的那个函数慢慢地回去向上操作. 可能 我们将 2 1 4 3 这4个元素 进行归并操作 那么我们是这样进行的吧
<2,1,4,3>---><2,1> , <4,3> <2,1>----><2.>,<1.> <4,3>----><4,>,<3>
先是要比较 2 和 1的大小关系 1小于2 那么先复制右边空间的数组 这里的左右以 Mid 为分界线 同时 如果是要进行逆序数对数个数统计的操作 那么这时候就需要mid-p了来计算此时左空间总共的数据个数这边不用担心会重复计算 因为当你左右空间全部遍历结束以后 它就会进行合并操作了 一起算到上一个更大的左/右区间之一了
--------恩 好像就暂时自己能想到这些地方吧 可能有错误 不可尽信 ..
不得不吐槽下 在写下上述东西的时候 垃圾电信 网断了大概6 7次 我草了...
hdu--4911--归并排序||树状数组