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

首先题目已经说的很明确了，输入一个数列，然后给这个数列排序。

直接调用 STL 的 sort 函数，用法是 sort(数组首地址,数组尾地址,排序方法) 排序方法可以不填，默认的从小到大排。

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000005];
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++)cin>>a[i];
    sort(a,a+m);
    for(int i=0;i<m;i++)cout<<a[i]<<" ";
    return 0;
}

时间复杂度 $O(m\log m)$。

---

我们看到 $n\le999$，可以考虑桶排序，开一个数组 $cnt$，用 $cnt_i$ 表示第 $i$ 个人获得的票数，读入一个数 $a$，就将 $cnt_{a}$ 加 $1$。

#include<bits/stdc++.h>
using namespace std;    
int n,m,a[1000005],cnt[1005];
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++)cin>>a[i],cnt[a[i]]++;
    for(int i=0;i<=1000;i++)while(cnt[i])cout<<i<<" ",cnt[i]--;
    return 0;
}

时间复杂度 $O(n+m)$，在值域小的时候跑得比 STL 快。