此题为模板题,考察对于二路归并算法的应用,常规写法为对数组进行归并排序,但我们可以利用OJ的Bug,将此题仅用几行代码写出来。即万能的stable_sort!
代码如下:
#include <bits/stdc++.h>
#pragma GCC optimize(2) //O2优化,不解释
long long a[1000001] , n;
using namespace std;
int main()
{
ios::sync_with_stdio(false); //加速读入,不解释
cin.tie(0); //加速读入,不解释
cin >> n;
for ( int i = 1 ; i <= n ; i ++ )
cin >> a[i];
stable_sort ( a + 1 , a + n + 1 ); //algorithm万岁!
for ( int i = 1 ; i <= n ; i ++ )
cout << a[i] << " ";
cout << endl;
return 0; //功德圆满~
}
Ps:此代码纯属娱乐,提高能力还需正常写归并代码,具体如下:
Code:
#include <bits/stdc++.h>
#pragma GCC optimize(2) //O2优化,不解释
using namespace std;
int n , a[500010] , c[500010];
long long ans;
void mergesort ( int b , int e )//归并排序
{
if ( b == e )
return ;
int mid = ( b + e ) / 2 , i = b , j = mid + 1 , k = b;
mergesort ( b , mid );
mergesort ( mid + 1 , e );
while ( i <= mid && j <= e )
if ( a[i] <= a[j] )
c[k++] = a[i++];
else
c[k++] = a[j++];
while ( i <= mid )
c[k++] = a[i++];
while ( j <= e )
c[k++] = a[j++];
for ( int l = b ; l <= e ; l ++ )
a[l] = c[l];
}
int main()
{
ios::sync_with_stdio(false); //优化读入,不解释
cin.tie(0); //优化读入,不解释
cin >> n;
for ( int i = 1 ; i <= n ; i ++ )
cin >> a[i];
mergesort ( 1 , n ); //归并排序
for ( int i = 1 ; i <= n ; i ++ )
cout << a[i] << " ";
cout << endl;
return 0; //功德圆满~
}
行