# 2021年1月APCS 4.飛黃騰達: Python一行解
## 題目敘述
https://zerojudge.tw/ShowProblem?problemid=f608
## 題目分析
1. 考慮以先比較 x 大小，再比較 y 大小的方式，對果實座標進行排序後的序列，其子序列的 x 座標滿足非嚴格遞增。
2. 對於排序後的結果，僅考慮其 y 座標，算出最長遞增子序列的長度，即為題目所求。
* 根據題設，x 座標和 y 座標僅要求非嚴格遞增。
* 綜合時間複雜度：$O(n\log(n))$
## 解題流程
輸入$\rightarrow$排序座標$\rightarrow$維護單調堆疊$\rightarrow$輸出
## 程式碼演示

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` `一行解`