[ProblemSolving]Baek Jun-1300 k 2番目の数値(バイナリナビゲーション)

提问链接

問題の説明

勢俊の大きさはN×N人配列Aをしました.配列内の数A[i][j]=i×jです.この数を主アレイBに入れると、Bの大きさはNとなる.×Nになる.Bを昇順に並べてみるとB[k]を求めてみる.
配列AとBのインデックスは1から始まる.

入力

最初の行は配列のサイズNを与える.Nは105以下の自然数である.2行目はkを与える.kはmin(109,N 2)の自然数以下である.

しゅつりょく

B[k]を出力します.

入力例1

3
7

サンプル出力1

6

私の答え

nは最大10,000であるため,ナビゲーション解でタイムアウト->이진 탐색で解決しよう!
5未満の数値123455246810223691215148121620115101520251
k=5の場合、B[k]=10、i=1~n
このとき、ある数以下の個数はmin(k/i,n)である.
ix 1, i x 2, i x 3, ix 4, ..... , i xjであるので、kをiで割った分は、その行において小さいか等しい個数であってもよい.
left=1とright=nxnを使用してmid(中値)を求め、파라메트릭 서치(이분탐색)を使用
k以下の最適個数を求める.

注意!

if  count(mid) >= k:
        answer = mid
        right = mid -1

条件文におけるcount(mid)=kとcount(mid)>kが分離しない原因はn=3,k=5,count(mid)=kが満たされないためである.
したがって、この問題は최적화된 문제를 결정문제로 풀어서 해결하는 파라메트릭 서치 유형と見なすことができる.이분 탐색がソートされた配列で完全に一致する値を返すと、파라메트릭 서치は最良の答えを見つけて返されます.

コード#コード#

n = int(input())
k = int(input())
def count(mid):
    cnt =0
    for i in range(1, n+1):
        cnt += min(mid//i, n)
    return cnt

left = 1 ;right = n*n
while left <= right:
    mid = (left +right)//2
    if  count(mid) >= k:
        answer = mid
        right = mid -1
    else:
        left = mid + 1
print(answer)