2021年1月APCS 4.飛黃騰達: Python一行解

題目敘述

https://zerojudge.tw/ShowProblem?problemid=f608

題目分析

1. 考慮以先比較 x 大小，再比較 y 大小的方式，對果實座標進行排序後的序列，其子序列的 x 座標滿足非嚴格遞增。
2. 對於排序後的結果，僅考慮其 y 座標，算出最長遞增子序列的長度，即為題目所求。

• 根據題設，x 座標和 y 座標僅要求非嚴格遞增。
• 綜合時間複雜度：
  $O(n\log (n))$

解題流程

輸入

$\to$排序座標

$\to$維護單調堆疊

$\to$輸出

程式碼演示

from bisect import bisect

def append(x): #維護單調堆疊的程序
    idx = bisect(mono, x)
    if idx==len(mono): mono.append(x)
    else: mono[idx] = x

mono = [] #單調堆疊
n = int(input())
seq = sorted(tuple(map(int, input().split())) for _ in range(n))

for _,i in seq: append(i)
print(len(mono))

Python 一行解

1. 將 for 迴圈寫成生成式
2. 將條件判斷改寫成三元運算，並將程序用函式包裝
3. 必要時將程序用函式包裝

#二分艘模組
from bisect import bisect
#二分搜尋
search = lambda i: bisect(mono, i)
#加入元素
append = lambda idx,i: mono.append(i) if idx==len(mono) else mono.__setitem__(idx, i)
#輸入
n, mono = int(input()), []; seq = sorted(tuple(map(int, input().split())) for _ in range(n))
#維護單調堆疊
tuple(append(search(i), i) for _,i in seq)
#輸出
print(len(mono))

最後再將這些程序用分號連接即可

from bisect import bisect; search, append = lambda i: bisect(mono, i), lambda idx,i: mono.append(i) if idx==len(mono) else mono.__setitem__(idx, i); n, mono = int(input()), []; seq = sorted(tuple(map(int, input().split())) for _ in range(n)); tuple(append(search(i), i) for _,i in seq); print(len(mono))

效率

原先程式碼：

一行解：

一行解的記憶體佔用稍多，效率上則跟原先程式碼無明顯區別

tags: Zerojudge APCS 202101 一行解