题解 P1271 【【深基9.例1】选举学生会】

TRZ_2007

2020-01-16 16:03:14

Solution

## Solution 这道题目本质上是排序…… 数据上说$m \le 2 \times 10^6$,所以我们可以基本排除$\Theta(n^2)$以上的算法,那么只有$sort,qsort,msort$以及其他我没说的排序了。 - 1 $sort$(谁都会,不讲) ``` #include <bits/stdc++.h> using namespace std; const int N = 2000010; int a[N],n; int m; int main() { scanf("%d %d",&m,&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1); for(int i=1;i<=n;i++) { printf("%d ",a[i]); } } ``` - 2: $qsort$ 主要是找到基准数并让其他数和它进行比较,以它为中心,左右分别是比他大和比他小的数。继续递归。 - 3:$msort$ 对这个数列进行分解,直到数据长度为一。接下来进行合并即可