题解 P1271 【【深基9.例1】选举学生会】
TRZ_2007
2020-01-16 16:03:14
## 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$
对这个数列进行分解,直到数据长度为一。接下来进行合并即可