CSUOJ2078-查找第k大(读入挂)

查找第k大

Submit Page Summary Time Limit: 1 Sec Memory Limit: 128 Mb Submitted: 316 Solved: 20

Description

小W有很强的好胜心，也有很明确的目标，总是希望当第k名，但是小W太菜了，经常达不到目标，于是他每次考试后都想知道第k名的分数是多少，然后以它为目标。现在给出了每个人的分数，请求编程能力很强的你帮他迅速找到第k名的分数为多少，这样他才有更多的时间去学习。

Input

第一行为一个正整数t代表有t组数据。每组数据第一行为两个正整数n和k，第二行为n个正整数。 1 < =k < =n < =107

Output

对于每组数据，输出第k大的数

Sample Input

1

6 2

1 2 3 4 5 6

Sample Output

Hint

#include<cstdio>

#include<algorithm>

namespace fastIO

{

	#define BUF_SIZE 100000

	bool IOerror = 0;

	inline char nc()

	{

		static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;

		 	if ( p1 == pend )

			 {

			  		p1	= buf;

					pend	= buf + fread( buf, 1, BUF_SIZE, stdin );

					if ( pend == p1 )

					{

							IOerror = 1;

							return(-1);

					}

			} 		

			return(*p1++); 	

	}

	inline bool blank( char ch )

	{

		return(ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t');

	}

	inline void rd( int &x )

	{

		char ch;

		while ( blank( ch = nc() ) )

		;

		if ( IOerror )

		return;

		for ( x = ch - '0'; (ch = nc() ) >= '0' && ch <= '9'; x = x * 10 + ch - '0' )

		;

	}

	#undef BUF_SIZE

};

using namespace fastIO;

using namespace std;

const int N = 1e7+10;

int arrNum[N];

int Partition(int *arrNum, int l, int r)

{

    if(arrNum == NULL || l > r)

	{

        return -1;

    }

    int mid = (l+r)>>1;

    swap(arrNum[mid], arrNum[r]);

    int leftSeqIndex = l;  

    for(int i = l; i < r; i++)

	{

        if(arrNum[i] < arrNum[r])

		{

           if(i > leftSeqIndex)

		   {

                swap(arrNum[i], arrNum[leftSeqIndex]);

           }

           ++leftSeqIndex;

        }

    }   

    swap(arrNum[leftSeqIndex], arrNum[r]);

    return leftSeqIndex;

}  

int GetNumber(int *arrNum, int n, int k)

{

    if(arrNum == NULL || n <= 0 || k <= 0 || k > n)

	{

        return -1;

    }  

    k = n-k+1;

    int l = 0;

    int r = n-1;

    while(l <= r)

	{

        int index = Partition(arrNum, l, r);

        if(index+1 == k)

		{

            return arrNum[index];

        }

        else if(index+1 < k)

		{

            l = index+1;

        }

        else

		{

            r = index-1;

        }

    }

}   

int main()

{

	int t,n,k;

	rd(t);

	while(t--)

	{

		rd(n);

		rd(k);

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

		{

			rd(arrNum[i]);

		}

		int value = GetNumber(arrNum, n, k);

		 	printf("%d\n",value);

	}

	return 0;

} 

/**********************************************************************

	Problem: 2078

	User: song_hai_lei

	Language: C++

	Result: AC

	Time:924 ms

	Memory:40280 kb

**********************************************************************/

巴特西