题解 | 统计数字-NOIP2007提高组复赛A题

这道题我的思路和别人不太一样，也许比较麻烦，但是思路特别好想。

首先根据输出样例，我们看到每一个数都对应了一个它所对应的出现次数。于是根据这一点，我们可以构建一个结构体：

“int k”代表输入的数，“int c”就是这个数对应的出现次数。这样我们就可以直接把数以及对应的出现次数一起输出，而免去了使用tot计数，而每次循环过后清零的麻烦（但是实际上使用tot计数的方法也有优点：占用内存小，速度会稍微快一点）。

主程序很简单，先将所有的数从小到大排序（满足从小到大输出的要求），之后从头到尾遍历每一个数，如果前一个数和后一个数大小相同，那么就可以将后一个数对应的出现次数，加上前一个数对应的出现次数（次数的初始值定为1， 这个我不用说），同时把前一个数清零。

这样，我们把所有不为零的数依次输出，同时输出对应的出现次数。由于一开始已经排过序，所以输出的数就是从小到大已经排序好的。

话不多说，看代码。（代码可能有些工程风格，同时也有测试输出的调试程序，但是相信大家也都能看懂）

#include <iostream>
#include<cstdio>
#include<algorithm>
const int maxN=1500000;
using namespace std;
struct node{
int k;
int c=1;
}a[maxN];
int n;
int cmp ( node b, node a){
return b.k<a.k;}
void INPUT()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i].k);
    return;
}
void work()
{
    sort(a+1,a+n+1,cmp);
    for (int i=1;i<=n;i++)
        {
            if(a[i].k==a[i+1].k)
        {
            a[i].k=0;
            a[i+1].c+=a[i].c;
        }
        if(a[i].k!=0)
            cout<<a[i].k<<" "<<a[i].c<<endl;
        }
    return;
}
int main()
{
    INPUT();
    work();
    /*for (int i=1;i<=n;i++)
        cout<<a[i].k<<" "<<endl;
    //cout << "Hello world!" << endl;*/
    return 0;
}