首页 > 试题广场 >

子集

[编程题]子集

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

小强现在有 $n$ 个物品,每个物品有两种属性 $x_i$ 和 $y_i$ .他想要从中挑出尽可能多的物品满足以下条件:对于任意两个物品 $i$ 和 $j$ ,满足 $x_i < x_j且y_i < y_j$ 或者 $x_i > x_j 且 y_i > y_j$ .问最多能挑出多少物品.

进阶：时间复杂度 $O(nlogn)\$ ，空间复杂度 $O(n)\$

输入描述:

第一行输入一个正整数.表示有组数据.
对于每组数据,第一行输入一个正整数.表示物品个数.
接下来两行,每行有个整数.
第一行表示个节点的属性.
第二行表示个节点的属性.

输出描述:

输出行,每一行对应每组数据的输出.

示例1

输入

2
3
1 3 2
0 2 3
4
1 5 4 2 
10 32 19 21

输出

2
3

算法知识视频讲解

Python

小伟，学习中......

Python3版本，但是超时了，有没有大佬帮优化下~

class Goods:

    def __init__(self, x, y):
        self.x = x
        self.y = y


class LIS:
    # 求最长上升子序列

    def __init__(self, array):
        self.array = array

    def find_lis(self):
        if self.array == []:
            return -1
        dp = [self.array[0].y]
        for a_idx in range(1, len(self.array)):
            if self.array[a_idx].y > dp[-1]:
                dp.append(self.array[a_idx].y)
            else:
                bs = BinarySerch(dp, self.array[a_idx].y)
                idx = bs.serch_by_recursion()
                dp[idx] = self.array[a_idx].y
        return len(dp)


class BinarySerch:
    # 二分查找

    def __init__(self, ordered_list, target):
        self.ordered_list = ordered_list
        self.target = target

    def serch_by_recursion(self):
        return self._recursion(0, len(self.ordered_list)-1)

    def _recursion(self, start, end):
        # if start > end:
        #     return start
        if start >= end:
            if self.target > self.ordered_list[start]:
                return start+1
            else:
                return start
        mid = start + (end-start)//2
        if self.target > self.ordered_list[mid]:
            return self._recursion(mid+1, end)
        elif self.target == self.ordered_list[mid]:
            return mid
        else:
            return self._recursion(start, mid-1)


if __name__ == "__main__":
    group_num = int(input())
    res = []
    for gn in range(group_num):
        goods_num = int(input())
        goods_x = input()
        goods_y = input()
        x_list = list(map(int, goods_x.split()))
        y_list = list(map(int, goods_y.split()))
        goods_list = []
        for index in range(len(x_list)):
            goods = Goods(x_list[index], y_list[index])
            goods_list.append(goods)
        goods_list.sort(key=lambda goods: (goods.x, -goods.y))
        lis = LIS(goods_list)
        print(lis.find_lis())

发表于 2022-09-06 11:26:16 回复(0)

Python

牛客257319613号

def insert(res, v):
        if len(res) == 0&nbs***bsp;v > res[-1]:
            res.append(v)
            return res
        if len(res) == 1:
            res[0] = v
            return res
        left, right = 0, len(res)-1
        while left < right-1:
            if res[(left+right)//2] >= v:
                right = (left+right)//2
            else:
                left = (left+right)//2
        res[right] = v
        return res
T=int(input())
for t in range(T):
    n = int(input())
    x = list(map(int, input().split()))
    y = list(map(int, input().split()))
    xy = list(zip(x,y))
    xy.sort(key=lambda x: x[0])
    y = [v[1] for v in xy]
    res = []
    for v in y:
        res = insert(res, v)
    print(len(res))

为什么测试不通过

发表于 2021-10-06 15:37:34 回复(2)

Python

牛客777207027号

给个 Python 能过的

from bisect import bisect_left
T = int(input())
for _ in range(T):
    n = int(input())
    X = map(int, input().split())
    Y = map(int, input().split())
    a = sorted(zip(X, Y), key=lambda x: (x[0], -x[1]))
    total = 0
    q = [0] * 100005
    for i in range(n):
        t = bisect_left(a=q, x=a[i][1], lo=0, hi=total)
        if t == total:
            total += 1
        q[t] = a[i][1]
    print(total)

假如用了 dataclass 会 TLE

from __future__ import annotations

from bisect import bisect_left
from dataclasses import dataclass


@dataclass
class node:
    x: int
    y: int

    def __lt__(self, other: node):
        if self.x != other.x:
            return self.x < other.x
        return self.y > other.y


T = int(input())
for _ in range(T):
    n = int(input())
    X = map(int, input().split())
    Y = map(int, input().split())
    a = sorted(node(*x) for x in zip(X, Y))
    total = 0
    q = [0] * 100005
    for i in range(n):
        t = bisect_left(a=q, x=a[i].y, lo=0, hi=total)
        if t == total:
            total += 1
        q[t] = a[i].y
    print(total)

编辑于 2021-05-03 03:12:10 回复(2)