python3 之 木棍加工

xiaosongliu · 2018-12-18 08:54:42 · 题解

不得不说库自带的函数很有用。C++的lower_bound；python 的bisect都是一样实现二分查找。 此题是很简单的最长非递减序列的动态规划。 先按照“宽”主关键字，“长”次关键字倒序排序。然后再从次关键字——“长”寻找最长递增序列。序列长度就是答案。（单调非递增的列数就等于单调递增长度——也可以写贪心实现）

import bisect
N = int(input())
s = []
t = input().split()
for i in range(N):
    s.append([int(t[i * 2]), int(t[i * 2 + 1])])
s.sort(key=lambda x: (x[0], x[1]), reverse=True)#排序
ans = [s[0][1]]
len = 1
for i in range(1, N):
    if s[i][1] > ans[len - 1]:
        ans.append(s[i][1])
        len += 1
    else:
        k = bisect.bisect_left(ans, s[i][1])#二分
        ans[k] = s[i][1]
print(len)