蒟蒻发题解了

说明：此题我用的方法为桶排（我翻了翻有人用了桶排只不过很难看出来，可能有些重复的，这个题只是作为一个专门的桶排来讲解吧）（不会算抄袭吧 ‘QWaWQ’）

简单来说（~~会的人跳过就行~~）：

桶排就是开两个数组，其中一个用来输入以及存储样例数列，另一个用来排序；

排序方法：(我用的第二个数组为b数组)

b[a[i]]=a[i]b[a[i]]=a[i]

核心代码（我认为的），先翻译一下：b数组为存储的那个桶，在b数组中第a[i]项的值为a[i]的值，这样等到下一个a[i]与b[a[i]]的值相同时就会重复赋值（我不会优化啊）从而实现了去重；

而在输出环节时用for循环；因为for的性质我们一般用

int i；i<=n;i++

来输出，i逐渐递增，用一个特判if(b[i]!=0)来判断是否在原数组中有赋值（题目给的是正整数，只要不等于零就有值）如果成立，输出就行，这样就实现了去重和排序双重功能！

没懂的多读几遍；

上AC代码！（25ms，0.8MB）

#include<iostream>

using namespace std;

int a[],k,n,i1,k1=,b[];

//a，b为上面提到的第一，第二个数组

int main(){

    cin>>n>>k;

    for(int i=;i<=n;i++)

    {

        cin>>a[i];//a数组的输入

        b[a[i]]=a[i];//核心代码

    }

    for(int i=;;i++)   //为何没循环条件？请看下文k1==k

    {

        if(b[i]!=)k1++;//用于计数的k1，计的时第几小的数

        if(k1==k)//条件：到了第k小的数

        {

            i1=i;//i1用于记录此时的i，因为i即b[a[i]]中a[i]的值

            break;//直接退了

        }

        else if(i==)

//很简单，数最大不到30000，如果i到了30000还没有到第k小的数，那就不可能存在了。如果不加这个条件会无限循环.

        {

            cout<<"NO RESULT";

            return ;//直接结束，不继续下文

        }

    }

    cout<<b[i1];//如果执行到了这一步，那么就存在k，直接输出第k个小的数就行。

    return ;

}

应该。。没问题了吧

巴特西

洛谷题解 P1138 【第k小整数】

蒟蒻发题解了

说明：此题我用的方法为桶排（我翻了翻有人用了桶排只不过很难看出来，可能有些重复的，这个题只是作为一个专门的桶排来讲解吧）（不会算抄袭吧 ‘QWaWQ’）

b[a[i]]=a[i]b[a[i]]=a[i]

int i；i<=n;i++

最新文章

热门文章

巴特西

洛谷题解 P1138 【第k小整数】

蒟蒻发题解了

说明：此题我用的方法为桶排（我翻了翻有人用了桶排只不过很难看出来，可能有些重复的，这个题只是作为一个专门的桶排来讲解吧） （不会算抄袭吧 ‘QWaWQ’）

b[a[i]]=a[i]b[a[i]]=a[i]

int i；i<=n;i++

最新文章

热门文章

说明：此题我用的方法为桶排（我翻了翻有人用了桶排只不过很难看出来，可能有些重复的，这个题只是作为一个专门的桶排来讲解吧）（不会算抄袭吧 ‘QWaWQ’）