SSL_1421&&P1138【第k小整数】

第k小整数

题目

P1138
备注：SSLOJ无数据范围，但数组开到100000能过，无需去重，输出位置而非值

---

解析

本题解采用了期望O(n)，最劣时O(n²)的快速排序变体，当然本题可以直接排序O(nlogn)水掉(SSLOJ结构体排序即可)，但为了不浪费自己的手写快排训练自己，写了一遍O(n)的变体(万一赛时出这题n<=10000000，岂不是当场去世)
思路:首先按照快排的方式排好，然后发现两段只有一段会产生结果，直接往那一段递归即可
1476K/0MS
最优解！
吐槽：这不是NOIP2008普及组初赛最后一题吗？

code(洛谷):

#include<cstdio>
#include<iostream>
using namespace std;
int n,a[10010],k,m;
bool f[30010];
inline int srt(int l,int r)
{
	if(l==r&&l==k)return a[k];
	int mid=a[l],i=l,j=r;
	while(i<j)
	{
		while(i<j&&a[j]>mid)j--;
		if(i<j)swap(a[i],a[j]);
		while(i<j&&a[i]<mid)i++;
		if(i<j)swap(a[i],a[j]);
	}
	a[i]=mid;
	return (i==k)?(a[k]):((i>k)?(srt(l,i-1)):(srt(i+1,r)));
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i){scanf("%d",&a[0]);if(!f[a[0]])f[a[++m]=a[0]]=1;}
	if(m<k)printf("NO RESULT");
	else printf("%d",srt(1,m));
	return 0;
}

code(SSLOJ):

#include<cstdio>
#include<iostream>
using namespace std;
int n,a[100010],id[100010],k;
inline int srt(int l,int r)
{
	if(l==r&&l==k)return id[k];
	int mid=a[l],i=l,j=r,iid=id[l];
	while(i<j)
	{
		while(i<j&&a[j]>mid)j--;
		if(i<j)swap(a[i],a[j]),swap(id[i],id[j]);
		while(i<j&&a[i]<mid)i++;
		if(i<j)swap(a[i],a[j]),swap(id[i],id[j]);
	}
	a[i]=mid,id[i]=iid;
	return (i==k)?id[k]:((i>k)?(srt(l,i-1)):(srt(i+1,r)));
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]),id[i]=i;
	printf("%d",srt(1,n));
	return 0;
}