2007提高。。。。。统计数组。。坑

题目:

某次科研调查时得到了n个自然数,每个数均不超过1500000000(1.5*10^9)。已知不相同的数不超过10000个,现在需要统计这些自然数各自出现的次数,并按照自然数从小到大的顺序输出统计结果。

数据范围:

40%的数据满足:1<=n<=1000
80%的数据满足:1<=n<=50000
100%的数据满足:1<=n<=200000,每个数均不超过1 500 000 000(1.5*109)


            看完数据范围就懵逼了····

            什么鬼数据,,,死大死大的,,

Time Limit Exceeded

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=233333;
int a[maxn]={},sum[maxn]={},shu[maxn];
int main()
{
    a[0]=0;
    int n,c=0,min,max,b=1;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+1+n);
    max=a[n];
    min=a[1];
    a[n+1]=0;
    for(int i=min;i<=max;i++)
    {
        int he=0;
        for(int j=b;j<=n;j++)
        {
            if(a[j]!=i)
                break;
            if(a[j]==i)
            {
                he++;
                sum[c]=he;
                shu[c]=i;
            }
            if(a[j]!=a[j+1])
            {
                c++;
                b=j+1;
                break;
            }
        }
    }
    for(int i=0;i<c;i++)
        cout<<shu[i]<<" "<<sum[i]<<endl;
    return 0;
}

好不容易想出来的,,,最后超时了。。心痛。。


但是,在聪明的我费尽心思之后终于想出了正确的代码!!!!

Accepted

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=233333;
int a[maxn]={},sum[maxn]={},shu[maxn],b[maxn]={};
int main()
{
    int n,c=0,d=0,he=0;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
    {
        if(a[i]!=b[d])
        {    
            d++;
            b[d]=a[i];
        }
    }
    d=1;
    for(int i=1;i<=n;i++)
    {
        if(a[i]==b[d])
        {
            he++;
            shu[d]=a[i];
            sum[d]=he;
        }
        if(a[i]!=a[i+1])
        {
            d++;
            he=0;
        }
    }
    for(int i=1;i<d;i++)
        cout<<shu[i]<<' '<<sum[i]<<endl;
    return 0;
}

为自己鼓掌!!!!!

啪啪啪啪啪啪啪啪啪啪啪啪啪啪啪啪啪啪啪啪

原文地址:https://www.cnblogs.com/zyker/p/5879212.html