Problem AB: STL 函数使用 —— stable_sort()

Problem AB: STL 函数使用 —— stable_sort()

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

SubmitProblemListSolved: 2Submit Num: 2StatisticsShowOff!

Description

【介绍】

【头文件】

Standard Template Library: Algorithms
#include<algorithm>

【作用】

Sort elements preserving order of equivalents
Sorts the elements in the range [first,last) into ascending order, like sort, but stable_sort preserves the relative order of the elements with equivalent values.
 The elements are compared using operator< for the first version, and comp for the second. 
template <class RandomAccessIterator>
  void stable_sort ( RandomAccessIterator first, RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>
  void stable_sort ( RandomAccessIterator first, RandomAccessIterator last,
                     Compare comp );
特别注意：该函数是稳定排序。

【时间复杂度】

$O(nlogn)$。

【任务】

我们通过本题，掌握 stable_sort() 函数使用方法。
给一个长度为 $n\ (1 \leq n \leq 5 \times 10^6)$ 的数列，请对数列进行排序。

Input

第一行包括一个整数 $n\ (1 \leq n \leq 5 \times 10^6),\ m\ (1 \leq n \leq 2)$。其中 $n$ 表示数列的长度，$m$ 表示排序方式，1 表示升序，2 表示降序。
第二行输入一个长度为 $n$ 的整数 $a_i\ (−10^9≤a_i≤10^9)$。

Output

输出只有一行，包括 $n$ 个整数，表示答案。

Sample 1 Input 

5 2
1 2 3 4 5

Sample 1 Output 

5 4 3 2 1

Sample 2 Input 

6 1
10 9 3 2 -1 -10

Sample 2 Output 

-10 -1 2 3 9 10
Submit