[NOIP 2007 提高组] 统计数字

知识点

排序、计数、游程统计

解题思路

将所有数字升序排序，扫描每段相同值，输出该值及连续段长度。

正确性说明

排序保留所有元素及重复次数，同值恰好连续，扫描每段输出其长度，便覆盖每个不同数字一次且按升序排列。

易错点

最后一段也要输出；数字值域大，不能按最大数直接开计数数组。

复杂度

时间O(n log n)，空间O(n)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin>>n;vector<long long>a(n);for(auto&x:a)cin>>x;sort(a.begin(),a.end());for(int i=0;i<n;){int j=i+1;while(j<n&&a[j]==a[i])j++;cout<<a[i]<<' '<<j-i<<'\n';i=j;}}