BOJ:半導体設計[2352]

ソース:[https://www.acmicpc.net/problem/2352 )

質問する

半導体を設計する場合、n個のポートを他のn個のポートに接続する必要がある場合がある.

たとえば、左の図は、n個のポートと他のn個のポートを接続する方法を示しています.ただし、このように接続すると、接続線は互いに絡み合っているので、このように接続することはできません.n個のポートが他のn個のポートにどのように接続されるかを指定する場合は、ベースラインの交差(オーバーラップ)を回避しながら、最大何個のポートに接続できるかを決定するプログラムを作成します.

入力

第1行は整数n(1≦n≦40000)を与える.次の行では、1番ポートに順次接続するポート番号、2番ポートに接続するポート番号、…、n番ポートに接続するポート番号を示します.これらの数が1以上n以下であると仮定し,等しくならない.

しゅつりょく

最初の行に最大接続数を出力します.

アイデア

リストの最後の値と比較して、リストの最後の値より大きい場合は、
大きくない場合はlow boundを使用します
low boundを使用して現在の値より大きいindexを取得

コード#コード#

Mine

import sys
input = sys.stdin.readline

n = int(input())
port = list(map(int, input().split()))
arr = []

def lower_bound(l, r, k):
    while l < r:
        m = (l + r) // 2
        if arr[m] < k:
            l = m + 1
        else:
            r = m
    return r

for i in range(n):
    if i == 0:
        arr.append(port[i])
    else:
        if port[i] > arr[-1]:
            arr.append(port[i])
        else:
            tmp = lower_bound(0, len(arr), port[i])
            arr[tmp] = port[i]

print(len(arr))

改善

Clone

from bisect import bisect
import sys
input = sys.stdin.readline
n = int(input())
s = list(map(int, input().split()))
dp = [s[0]]
for i in range(1, n):
    if s[i] > dp[-1]:
        dp.append(s[i])
    else:
        dp[bisect(dp, s[i])] = s[i]
print(len(dp))

ソース:https://pacific-ocean.tistory.com/353

改善