题解 P1059 【明明的随机数】

· · 题解

这道题目，要求还是有点多的，乍一看也许毫无思路（冒泡，插入，归并等排序可能需要些很长的程序，而且还有可能错）。那么，请大家请出我们今天的嘉宾————桶排！！！

什么是桶排？？

对于桶排的理解，我们不妨假设一个情景：地上散落着一些玩具，你把这些玩具按名称分类依次放进一个桶里，当别人来问你有哪几种玩具时，你只需要将每个桶中拿出一个玩具就可以了。 C++也是这样，只要开一个数组，将每个数装在相应的“桶”里，输出时只要按照顺序，看看“桶”里有没有存储的数，有则输出，无则跳过。这个过程就叫桶排序。 桶排程序如下

    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>r[i];
        a[r[i]]++;
    }
    for(int i=1;i<=1000;i++){
        if(a[i]>0){
            cout<<i<<" ";
        }
    }
    return 0;
}

但对于另一种题目来说，要将所有数排序，其实也没有什么差别，只要加上一句话就可以了。 程序如下：

    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>r[i];
        a[r[i]]++;
    }
    for(int i=1;i<=1000;i++){
        if(a[i]){
            for(int i=a[i];i>0;i--){
                cout<<i<<" ";
            }
        }
    }
    return 0;
}

没错，就是要加上一个循环，来检测桶内还有没有数未输出。

桶排有没有弊端？？

任何一种排序方法都是有弊端的，桶排也是一样。因为桶排需要将数一个个装进桶里，也就是说桶可能会有上百万甚至千万，亿个。大家可以试想一下在一个操场上方一百万个桶的样子，肯定是放不下的。那么桶排的弊端就很明显了：占用空间太大，容易造成空间超限。 当输入数据最大不超过100000时可以使用桶排，但如果数据到达了100000<n<1000000时最好不要使用，可能会超空间。当数据达到了1000000以上绝对不能使用桶排，否则一个大大的MLE摆在上面也是挺尴尬的。 错误范例：

#include<bits/stdc++.h>
using namespace std;
int r[5000000];
int a[5000000];//数组超限，MLE
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>r[i];
        a[r[i]]++;
    }
    ......
    return 0;
}

有没有办法可以避免

目前来说，还没有办法可以避免桶排的弊端。当你尝试将数组压缩到100000以下，那遇到某些数据大于100000的将不会算入，输出时可能会打出一堆乱码。 那有人会说了：“我可以用插入法来将数据放进‘桶’啊。”但这还是一个问题：第一点，这已经不再属于桶排了，而属于直接插入排序了。第二点,当不同的数据超过了100000个，同样会有一些数不被统计到，导致输出故障。 错误范例：

int r[500];
int a[500];//数组过小，对于大于500的数据无法统计到
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>r[i];
        a[r[i]]++;
    }
    ......
    return 0;
}

所以用桶排就循规蹈矩地用，不要进行那些无用的“创新”，反而会使你的程序出现更多漏洞。（同时细节方面也要注意）。

你们要的程序

前面介绍了那么多关于桶排的事项，大家都等不及了吧。下面就是大家期待的程序。 程序如下：

#include<bits/stdc++.h>
using namespace std;
int r[5000];
int a[5000];//根据题意，数组至少开到1001，我开5000是为了保险
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>r[i];//读入数据
        a[r[i]]++;//放入“桶”内
    }
    int t=0;//题目要求，要统计共有多少个不同的数据。
    for(int i=1;i<=1000;i++){
        if(a[i]>0){
            t++;//当检测到第i个桶里有数时，t值+1。
        }
    }
    cout<<t<<endl;
    for(int i=1;i<=1000;i++){
        if(a[i]>0){
            cout<<i<<" ";//当检测到第i个桶里有数时，输出桶的序号
        }
    }
    return 0;//结束程序
}

拓展

能否用冒泡，快排，归并等方法做出这道题？答案是当然可以。这里就不再做介绍，有兴趣的读者可以尝试去做，了解或巩固其他的排序方法。