搭积木

[编程题]搭积木

热度指数：18759 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小明有一袋子长方形的积木，如果一个积木A的长和宽都不大于另外一个积木B的长和宽，则积木A可以搭在积木B的上面。好奇的小明特别想知道这一袋子积木最多可以搭多少层，你能帮他想想办法吗？

定义每一个长方形的长 L 和宽 W ，袋子里面长方形的个数为 n 。

假如袋子里共有5个积木分别为 (2, 2), (2, 4), (3, 3), (2, 5), (4, 5), 则不难判断这些积木最多可以搭成4层, 因为(2, 2) < (2, 4) < (2, 5) < (4, 5)。

数据范围：长方形个数满足 $1 \le n \le 10^6 \$ ， $1 \le w \le l \le 2^{31}-1 \$

输入描述:

第一行为积木的总个数 N

之后一共有N行，分别对应于每一个积木的宽W和长L

输出描述:

输出总共可以搭的层数

示例1

输入

输出

算法知识视频讲解

Python

sky游荡

这题真是神奇，卡极限时间的，同样的代码先后提交还有前一次过了后一次就过不了的。

一开始先直接动态规划，超时，后来改进了下，用最长上升子序列的思想，用二分，然后超内存，接着听说用tuple可以降内存，然后***又超时了，最后没办法用了自带的库bisect进行二分查找，就这还有得时候超时。

import bisect 
n = int(input())
data = []
for i in range (n):
    w,l=map(int,input().split(' '))
    data.append((w,l))
data = sorted(data)
###data = [data[i][1] for i in range(len(data))]
binary = []
for i in range(len(data)):
    if not binary:
        binary.append(data[i][1])
    elif binary[-1] <= data[i][1]:
        binary.append(data[i][1])
    else:
        index = bisect.bisect_left(binary,data[i][1])
        binary[index] = data[i][1]
print(len(binary))

编辑于 2020-04-13 01:18:06 回复(1)