search

yosupo06 / library-checker-problems

The problem data (Test case generator, judge's solution, task, ...) of Library Checker
https://judge.yosupo.jp/
Apache License 2.0
524 stars 118 forks source link

[問題案] Kth Smallest #856

Open SSRS-cp opened 2 years ago

SSRS-cp commented 2 years ago

問題名: Kth Smallest 問題 ID: kth_smallest 想定アルゴリズム: median of medians

問題文

長さ N の数列 a_0, a1, ..., a{N-1} と整数 k が与えられる。(a_0, a1, ..., a{N-1}) のうち k+1 番目に小さい値を求める。

制約

1<=N<=5*10^5 0<=a_i<=10^9 0<=k<N

tko919 commented 2 years ago

Range Kth SmallestにQ=1,L=0,R=Nのケースを追加すれば兼用できそうです

yosupo06 commented 2 years ago

↑のtkoさんのやつか、もしくはk番目取得よりは1-k番目取得の方がよく見るトピックな気がします

yosupo06 commented 2 years ago

結果ははsortされてなくてもいいというやつです(O(N)でできるという話

maspypy commented 9 months ago

特にこれを verify したいという話を（問題提案者を含めて）見かけていないため、優先度は低そうですが、準備に興味がある型が居ればお願いします。