首页 > 代码库 > ACdream 1099求第k大

ACdream 1099求第k大

2024-07-15 10:49:42   216人阅读

题目链接

瑶瑶的第K大

Time Limit: 10000/5000MS (Java/Others)Memory Limit: 512000/256000KB (Java/Others)
SubmitStatisticNext Problem

Problem Description

一天，萌萌的妹子--瑶瑶(tsyao)很无聊，就来找你玩。可是你们都不知道玩什么。。。尴尬了一阵子，机智的瑶瑶就提议：“这样吧，你说N个整数xi，然后在随意说一个数字k，我能够快速地说出这些数字里面第 k 大的数字。”

Input

第1行 两个整数N, K以空格隔开；

第2行 有N个整数（可出现相同数字，均为随机生成），同样以空格隔开。

0 < n ≤ 5*10^6 , 0 < k ≤ n

1 ≤ xi ≤ 10^8

Output

输出第 k 大的数字。

Sample Input

5 25 4 1 3 1

Sample Output

4

Hint

如2，2，1中三个数字中第一大数字为2，第二大数字也为2，第三大数字为1 。
由于n过大，需要使用输入挂，然后O(n)的快速选择即可。1A
Accepted Code:
 1 /************************************************************************* 2     > File Name: Kth.cpp 3     > Author: Stomach_ache 4     > Mail: sudaweitong@gmail.com 5     > Created Time: 2014年08月02日 星期六 12时32分04秒 6     > Propose: ACdream 7  ************************************************************************/ 8 //输入挂+快速选择 9 #include <cmath>10 #include <string>11 #include <cstdio>12 #include <fstream>13 #include <cstring>14 #include <iostream>15 #include <algorithm>16 using namespace std;17 18 int n, k;19 int a[5000002];20 21 int read() {22       int x = 0;23     char ch = ‘ ‘;24     while (ch < ‘0‘ || ch > ‘9‘) ch = getchar();25     while (ch >= ‘0‘ && ch <= ‘9‘) x = x * 10 + ch - ‘0‘, ch = getchar();26     return x;27 }28 29 int sort(int l, int r) {30       if (l >= r) return a[l];31       int pivot = a[(l+r)/2];32     int i = l, j = r;33     for ( ; ; ) {34           while (i < j && a[i] <= pivot) i++; 35         while (i < j && a[j] >= pivot) j--;36         if (i < j) swap(a[i], a[j]);37         else break;38         i++; j--;39     }40     swap(a[i], a[(l+r)/2]);41     if (i == k) return a[i];42     if (i < k) return sort(i+1, r);43     else return sort(l, i-1);44 }45 46 int main(void) {47       while (~scanf("%d %d", &n, &k)) {48           for (int i = 1; i <= n; i++) 49               a[i] = read();50         k = n - k + 1;51         int ans = sort(1, n);52         printf("%d\n", ans);53     }54     return 0;55 }

 


联系
我们