最新公告
  • 欢迎您光临信息学奥赛网,一个优质的信息学编程题库和信息学编程学习资源专业网站。欢迎加入VIP
  • 俄罗斯套娃

    正文概述 陈老师   2026-01-20 15:16:05  

    题目描述

    给定一个大小为nn的二维数组aa,其中格式大概为这个样子:ai=[wi,hi]a_i = [w_i, h_i]标识我们第ii个信封的宽度和高度。

    当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗斯套娃一样。

    请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封(即可以把一个信封放到另一个信封里面)。

    注意:不允许旋转信封

    输入描述

    第一行一个整数nn代表数组的大小。

    接下来nn行每行两个整数分别代表wi,hiw_i, h_i

    输出描述

    输出一行一个整数表示答案。

    样例

    4
    5 4
    6 4
    6 7
    2 3
    
    3
    

    样例解释:

    最多信封的个数为 33, 组合为: [2,3]=>[5,4]=>[6,7][2,3] => [5,4] => [6,7]

    数据范围

    1n,wi,hi1051 \le n, w_i, h_i \le 10^{5}

    信息学奥赛网,一个优质的信息学奥赛学习资源平台!
    信息学奥赛网 » 俄罗斯套娃