基础算法 快速排序 函数模板 void quick_sort ( int q [], int l , int r )
{
if ( l >= r ) return ;
int i = l - 1 , j = r + 1 , x = q [ l + r >> 1 ];
while ( i < j )
{
do i ++ ; while ( q [ i ] < x );
do j -- ; while ( q [ j ] > x );
if ( i < j ) swap ( q [ i ], q [ j ]);
}
quick_sort ( q , l , j ), quick_sort ( q , j + 1 , r );
}
Copy 完整程序 # include <iostream>
using namespace std ;
const int N = 1e6 + 10 ;
int n ;
int q [ N ];
void quick_sort ( int q [], int l , int r )
{
if ( l >= r ) return ;
int x = q [ l ], i = l - 1 , j = r + 1 ; // i 从 l-1 开始,保证 do i++ 后,i 第一个访问的是 l
while ( i < j ){
do i ++ ; while ( q [ i ] < x );
do j -- ; while ( q [ j ] > x );
if ( i < j ) swap ( q [ i ], q [ j ]);
}
quick_sort ( q , l , j );
quick_sort ( q , j + 1 , r );
}
int main ()
{
scanf ( "%d" , & n );
for ( int i = 0 ; i < n ; i ++ ) scanf ( "%d" , & q [ i ]);
quick_sort ( q , 0 , n - 1 ); // 0 和 n-1 是左右边界的索引
for ( int i = 0 ; i < n ; i ++ ) printf ( "%d " , q [ i ]);
return 0 ;
}
Copy 归并排序 函数模板 void merge_sort ( int q [], int l , int r )
{
if ( l >= r ) return ;
int mid = l + r >> 1 ; // (l + r) / 2
merge_sort ( q , l , mid );
merge_sort ( q , mid + 1 , r );
int k = 0 , i = l , j = mid + 1 ;
while ( i <= mid && j <= r )
if ( q [ i ] <= q [ j ]) tmp [ k ++ ] = q [ i ++ ];
else tmp [ k ++ ] = q [ j ++ ];
while ( i <= mid ) tmp [ k ++ ] = q [ i ++ ];
while ( j <= r ) tmp [ k ++ ] = q [ j ++ ];
for ( i = l , j = 0 ; i <= r ; i ++ , j ++ ) q [ i ] = tmp [ j ];
}
Copy 完整程序 #include <iostream>
using namespace std ;
const int N = 1000010 ;
int n ;
int q [ N ], tmp [ N ];
void merge_sort ( int q [], int l , int r )
{
if ( l >= r ) return ;
int mid = ( l + r ) >> 1 ;
merge_sort ( q , l , mid ), merge_sort ( q , mid + 1 , r );
int k = 0 , i = l , j = mid + 1 ;
while ( i <= mid && j <= r ){
if ( q [ i ] <= q [ j ]) tmp [ k ++ ] = q [ i ++ ];
else tmp [ k ++ ] = q [ j ++ ];
}
while ( i <= mid ) tmp [ k ++ ] = q [ i ++ ];
while ( j <= r ) tmp [ k ++ ] = q [ j ++ ];
for ( i = l , j = 0 ; i <= r ; i ++ , j ++ ) q [ i ] = tmp [ j ];
}
int main ()
{
scanf ( "%d" , & n );
for ( int i = 0 ; i < n ; i ++ ) scanf ( "%d" , & q [ i ]);
merge_sort ( q , 0 , n - 1 );
for ( int i = 0 ; i < n ; i ++ ) printf ( "%d " , q [ i ]);
return 0 ;
}
Copy 整数二分 函数模板 bool check ( int x ) { /* ... */ } // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int bsearch_1 ( int l , int r )
{
while ( l < r )
{
int mid = l + r >> 1 ;
if ( check ( mid )) r = mid ; // check()判断mid是否满足性质
else l = mid + 1 ;
}
return l ;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int bsearch_2 ( int l , int r )
{
while ( l < r )
{
int mid = l + r + 1 >> 1 ; // 是否加1取决于是 l = mid 还是r = mid,和其他因素无关
if ( check ( mid )) l = mid ;
else r = mid - 1 ;
}
return l ;
}
Copy 完整程序 #include <iostream>
using namespace std ;
const int N = 100010 ;
int n , m ;
int q [ N ];
int main ()
{
scanf ( "%d%d" , & n , & m );
for ( int i = 0 ; i < n ; i ++ ) scanf ( "%d" , & q [ i ]);
while ( m -- )
{
int x ;
scanf ( "%d" , & x );
int l = 0 , r = n - 1 ;
while ( l < r )
{
int mid = l + r >> 1 ;
if ( q [ mid ] >= x ) r = mid ;
else l = mid + 1 ;
}
if ( q [ l ] != x ) cout << "-1 -1" << endl ;
else
{
cout << l << ' ' ;
int l = 0 , r = n - 1 ;
while ( l < r )
{
int mid = l + r + 1 >> 1 ;
if ( q [ mid ] <= x ) l = mid ;
else r = mid - 1 ;
}
cout << l << endl ;
}
}
return 0 ;
}
Copy 浮点数二分 函数模板 bool check ( double x ) { /* ... */ } // 检查x是否满足某种性质
double bsearch_3 ( double l , double r )
{
const double eps = 1e-6 ; // eps 表示精度,取决于题目对精度的要求
while ( r - l > eps )
{
double mid = ( l + r ) / 2 ;
if ( check ( mid )) r = mid ;
else l = mid ;
}
return l ;
}
Copy 完整程序 #include <iostream>
using namespace std ;
int main ()
{
double x ;
cin >> x ;
double l = - 100 , r = 100 ;
while ( r - l > 1e-8 )
{
double mid = ( l + r ) / 2 ;
if ( mid * mid * mid >= x ) r = mid ;
else l = mid ;
}
printf ( "%.6lf \n " , l );
return 0 ;
}
Copy xx 函数模板 完整程序