白駿1300号「K回数」

3368 ワード
アルゴリズム#アルゴリズム# テキストリンク

質問する


白俊1300番K番目の数。

に答える


初めて問題を見たとき、直接2つの複文を回して、2次元配列を作成して、昇順に並べて問題を解いて、結果はメモリが超過していることを示しました...
要するに、この方式があまりにも非効率であることに気づいて、検索してみると、この問題もこの探索問題であることに気づいた.
1次元配列を昇順に配置してxという数値を検索すると、xのインデックスはx以下の数値の後になります.
すなわち,x以下のすべての数字を見つければ,xの位置を知ることができる.

5*5サイズの配列を描き、考えてみましょう.
検索する数xが12の場合、1行あたり12未満の数は12/行インデックスのパーセントです(列の最大サイズは5、5を超える場合は5).
これを用いて二分探索を行い,特定のmid値のインデックスが与えられたk値と同じである場合に見つければよい.

Pythonコード

import sys
input = sys.stdin.readline

n = int(input())
k = int(input())
left, right = 1, k

while left <= right:
  mid = (left + right) // 2
  tmp = 0

  for i in range(1, n+1):
    tmp += min(mid//i, n)

  if tmp >= k:
    ans = mid
    right = mid -1
  else:
    left = mid + 1

print(ans)
[アルゴリズム]平均値を求める
白駿1316-組合せ語checker