パイ

1107 ワード
binary_search python テキストリンク 
import bisect
対分はバイナリ検索アルゴリズムを実現するモジュールである
bisect.bisect関数は、ソートされたリストに値を挿入したときにソートを維持できるインデックスを返します.
https://www.acmicpc.net/problem/11053
dp問題に分類されていますが、対分的に解答しました
bisect_left(a, x)
検索リストaに挿入するデータxの一番左のインデックスは、
  • の並べ替えを保持したままである.
    例えば、与えられた入力が「10 20 10 30 20 50」である場合
    リスト[0]、リスト[1]番号(dp=[10,20])が順番に挿入されます.
    リスト[2]に遭遇した場合、前の位置の値より小さいため、挿入リスト[2]に挿入されたインデックスを見つけることができます.
    idx = bisect.bisect_left(dp, arr[i])
    この場合、idxは0(現在のdp[0]回は10)である
    ペアリングを使用して解く
    import sys
import bisect

n = int(input())

seq = list(map(int, sys.stdin.readline().split()))
dp = [seq[0]]

for i in range(1, n):
    if seq[i] > dp[-1]:
        dp.append(seq[i])
    else:
        idx = bisect.bisect_left(dp, seq[i])
        dp[idx] = seq[i]

print(len(dp))
    • [TIL] Day36- Web Server(3)
    プライベートネームスペース単一インスタンスプログラムの作成