洛谷题解 P1138 【第k小整数】 蒟蒻发题解了
说明：此题我用的方法为桶排（我翻了翻有人用了桶排只不过很难看出来，可能有些重复的，这个题只是作为一个专门的桶排来讲解吧） （不会算抄袭吧 ‘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[10001],k,n,i1,k1=0,b[30000]; //a，b为上面提到的第一，第二个数组 int main(){ cin>>n>>k; for(int i=1;i<=n;i++) { cin>>a[i];//a数组的输入 b[a[i]]=a[i];//核心代码 } for(int i=1;;i++) //为何没循环条件？请看下文k1==k { if(b[i]!=0)k1++;//用于计数的k1，计的时第几小的数 if(k1==k)//条件：到了第k小的数 { i1=i;//i1用于记录此时的i，因为i即b[a[i]]中a[i]的值 break;//直接退了 } else if(i==30000) //很简单，数最大不到30000，如果i到了30000还没有到第k小的数，那就不可能存在了。如果不加这个条件会无限循环. { cout<<"NO RESULT"; return 0;//直接结束，不继续下文 } } cout<<b[i1];//如果执行到了这一步，那么就存在k，直接输出第k个小的数就行。 return 0; }
应该。。没问题了吧