不守秩序的站队者

发布时间:2016-12-9 21:29:16 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"不守秩序的站队者",主要涉及到不守秩序的站队者方面的内容,对于不守秩序的站队者感兴趣的同学可以参考一下。

/* 多人排成一个队列 , 我们认为从低到高是正确的序列 , 但是总有部分人不遵守秩序。 如果说 , 前面的人比后面的人高 ( 两人身高一样认为是合适的 ), 那么我们就认为这两个人是一对 “ 捣乱分子 ” , 比如说 , 现在存在一个序列 : 176, 178, 180, 170, 171 这些捣乱分子对为 <176, 170>, <176, 171>, <178, 170>, <178, 171>, <180, 170>, <180, 171>, 那么 , 现在给出一个整型序列 , 请找出这些捣乱分子对的个数 */ //归并排序 #include<iostream> using namespace std; int _sum; void merge( int * list , int s , int m , int t ){ int * left; int * right; int len_left = m - s + 1; int len_right = t - m; int i , j , k; left = ( int * ) malloc( len_left * sizeof( int ) ); right = ( int * ) malloc( len_right * sizeof( int ) ); for( i = 0 , j = s ; i < len_left ; i ++ ) { left[ i ] = list[ j ++ ]; } for( i = 0 , j = m + 1 ; i < len_right ; i ++ ) { right[ i ] = list[ j ++ ]; } i = 0; j = 0; k = s; while( ( i < len_left ) && ( j < len_right ) ) { if( left[ i ] <= right[ j ] ) { list[ k ++ ] = left[ i ++ ]; } else { list[ k ++ ] = right[ j ++ ]; _sum += ( len_left - i ); } } while( i < len_left ) { list[ k ++ ] = left[ i ++ ]; } while( j < len_right ) { list[ k ++ ] = right[ j ++ ]; } free( left ); free( right ); } void mergeSort( int *list , int s , int t ) { if( s < t ){ int m = ( s + t ) / 2; mergeSort( list , s , m ); mergeSort( list , m + 1 , t ); merge( list , s , m , t ); } return; } int main() { int i = 0; _sum = 0; int list[ 10 ]; for( i = 0 ; i < 10 ; i++ ) { cin >> list[ i ]; } mergeSort( list , 0 , 9 ); cout << _sum << endl; return 1; } //176 178 177 174 172 180 185 188 191 177

上一篇:NC打补丁什么情况下需要部署
下一篇:win32多线程程序设计笔记(第五章)

相关文章

相关评论