ACdream 1099第kの大きいことを求めます
9251 ワード
タイトルリンク
ヤオヤオのK番目の大きさ
Time Limit: 10000/5000MS (Java/Others)Memory Limit: 512000/256000KB (Java/Others)
Submit Statistic Next Problem
Problem Description
ある日、萌え萌えの女の子--瑶瑶(tsyao)は退屈で、遊びに来ました.しかし、あなたたちは何を游んでいるのか分かりません..しばらく気まずい思いをして、機知の瑶瑶は提案します:“このようにしましょう、あなたはN個の整数xiを言って、それから勝手に1つの数字kを言って、私は急速にこれらの数字の中で第 k 大きな数字です.」
Input
行1 2つの整数N、Kはスペースで区切られている.
2行目 N個の整数(同じ数字が表示され、ランダムに生成されます)があり、同じようにスペースで区切られています.
0 < n ≤ 5*10^6 , 0 < k ≤ n
1 ≤ xi ≤ 10^8
Output
出力第 k 大きな数字.
Sample Input
Sample Output
Hint
例えば2,2,1の3つの数字のうち1番目に大きい数字は2で、2番目に大きい数字も2で、3番目に大きい数字は1です. .
nが大きすぎるため、入力フックを使用し、O(n)の迅速な選択が必要です.1A
Accepted Code:
ヤオヤオのK番目の大きさ
Time Limit: 10000/5000MS (Java/Others)Memory Limit: 512000/256000KB (Java/Others)
Submit Statistic Next Problem
Problem Description
ある日、萌え萌えの女の子--瑶瑶(tsyao)は退屈で、遊びに来ました.しかし、あなたたちは何を游んでいるのか分かりません..しばらく気まずい思いをして、機知の瑶瑶は提案します:“このようにしましょう、あなたはN個の整数xiを言って、それから勝手に1つの数字kを言って、私は急速にこれらの数字の中で第 k 大きな数字です.」
Input
行1 2つの整数N、Kはスペースで区切られている.
2行目 N個の整数(同じ数字が表示され、ランダムに生成されます)があり、同じようにスペースで区切られています.
0 < n ≤ 5*10^6 , 0 < k ≤ n
1 ≤ xi ≤ 10^8
Output
出力第 k 大きな数字.
Sample Input
5 2
5 4 1 3 1
Sample Output
4
Hint
例えば2,2,1の3つの数字のうち1番目に大きい数字は2で、2番目に大きい数字も2で、3番目に大きい数字は1です. .
nが大きすぎるため、入力フックを使用し、O(n)の迅速な選択が必要です.1A
Accepted Code:
1 /************************************************************************* 2 > File Name: Kth.cpp 3 > Author: Stomach_ache 4 > Mail: [email protected] 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
", ans); 53 } 54 return 0; 55 }