摘要：根据题意，我们只需要将所有选票从小到大排序即可。可是最多有2百万张票，sort函数的时间复杂度为O(nlogn)，排序的时间会稍稍超时。
选举学生会
算法解析
1、根据题意，我们只需要将所有选票从小到大排序即可。可是最多有2百万张票，sort函数的时间复杂度为O(nlogn)，排序的时间会稍稍超时。
2、由于人数不超过1000，可以考虑计数排序（即每种元素放一个桶的桶排序），利用数组下标是有序的特点，用数组下标表示候选人编号，元素的值表示选票张数，最后按顺序输出即可。
3、普通的计数排序算法不够稳定，并且可能会造成内存浪费，因此可以结合前缀和算法改良计数排序，使其更加稳定。
【参考代码】
//此为计数排序改良版代码#includeusing namespace std;int a[2000005],cnt[1000],b[2000005];int main{ int n,m; cin>>n>>m; int mina=1000,maxa=0; for(int i=0;i>a[i]; mina=min(mina,a[i]); maxa=max(maxa,a[i]); } int num=maxa-mina+1; for(int i=0;i=0;i--){ b[cnt[a[i]-mina]]=a[i]; cnt[a[i]-mina]--; } for(int i=1;i代码中的C++知识解读
前缀和算法
前缀和是一种常见的数组处理技巧，它将数组中的元素依次累加得到新数组，新数组的第i个元素表示原数组前i项的和。
设原数组为a[n]，前缀和数组为s[n]，首先推导：
s[0]=a[0]
s[1]=a[0]+a[1]=s[0]+a[1]
s[2]=a[0]+a[1]+a[2]=s[1]+a[2]
s[3]=a[0]+a[1]+a[2]+a[3]=s[2]+a[3]
……
根据递推思想，可以得到前缀和的递推公式为：
s[i]=s[i-1]+a[i]
根据递推公式可以快速写出维护前缀和数组的代码：
a[0]=0,s[0]=0;for(int i=1;i>a[i]; s[i]=s[i-1]+a[i]; //根据递推公式，i必须大于0，否则i-1前缀和最主要的功能是计算数组某个区间所有数字之和。例如想要计算a数组从第x个元素到第y个元素的和，普通的做法是：
int sum=0;for(int i=x;i通过循环语句实现相加。但是如果维护好了前缀和数组，可以直接这么写：
int sum=s[y]-s[x-1];//前y项的和减掉前x-1项的和就是x到y所有元素的和是不是代码更加简洁了呢？同时将时间复杂度为O(n)的数组区间和的计算优化到了O(1)。
在实际算法设计中，前缀和自身的应用其实不多，使用更多的还是根据前缀和引申出来的算法技巧——差分。
★差分是一种处理数据的简单又巧妙的方法，主要应用于区间的查询和修改问题，能将普通的遍历做法优化为2个端点的修改，并优化时间复杂度到O(1)。
运行结果
在“排序”题单中，大部分的题目可以直接使用sort函数完成数据的排序
但是，如果题目很明显能用某种排序算法解决问题的话（例如本题是计数排序），还是建议读者们写一写对应的排序算法代码，强化对各算法的理解。
来源：小美课堂
