[编程题]神秘礼物描述 Peter为了祝他的澳大利亚朋友生日快乐，想要给他寄了一张贺卡。为了让礼物更有神秘感，他决定做一个“套娃信封”。所谓的“套娃信封”是指：假设贺卡的宽度和高度分别为 w 和 h，为了将

当前位置：首页 > 题库 > 学习训练 > C/C++

题目信息

题目类型: 练习
题目年份: 2025

题目题型: 编程题
关键词: 神秘礼物

题目题干

描述

Peter为了祝他的澳大利亚朋友生日快乐，想要给他寄了一张贺卡。为了让礼物更有神秘感，他决定做一个“套娃信封”。
所谓的“套娃信封”是指：假设贺卡的宽度和高度分别为 w 和 h，为了将贺卡放入第一层信封，第一层信封的宽度 w₁ 和高度 h₁ 应当满足 w₁>w, h₁>h。为了将第一层信封装入第二层信封中，第二层信封的宽度 w₂ 和高度 h₂ 应当满足 w₂>w₁, h₂>h₁。以此类推 ……
Peter现在有 n 个信封，每个信封的宽度和高度已知，他想请你帮他选出一些信封，组成一个层数最大的“套娃信封”，并将方案输出。

输入

第一行包含三个整数 n,w 和 h(1 ≤ n ≤ 5000, 1 ≤ w,h ≤ 10^6)，分别表示Peter拥有的信封个数，贺卡的宽度和高度。

接下来 n 行，每行两个整数，第 i+1 行为 wi 和 hi( 1 ≤ wi,hi ≤ 10^6)，表示第 i 个信封的宽度和高度。

输出

第一行输出“套娃信封”的最大层数。

第二行从第一层信封（尺寸最小的信封）的编号开始，输出组成“套娃信封”的信封编号（用空格隔开）。请注意，贺卡只能放入第一层信封中。如果方案不是唯一的，输出任何一个方案均可。

如果贺卡无法装入任何一个信封，则只需在第一行输出数字 0 并且不用输出第二行的方案。

样例输入

样例输出

输出#1
1
1 

输出#2
3
1 3 2

提示

【解释#1】

Peter的两个信封尺寸一样，因此最多只能套一层信封。注意对于样例#1，第二行输出 2 也是合法的答案。

【解释#2】

Peter选出这所有的三个信封，然后将贺卡放在信封1中，信封1套在信封3中，再将信封3套在信封2中。

【数据范围】

对于 20% 的数据，n ≤ 9；

额外有 30% 的数据，保证 w1 < w2 < ... < wn；

对于 100% 的数据，1 ≤ n ≤ 5000, 1 ≤ w,h,wi,hi ≤ 10^6。

答案解析

提示声明

免责声明：本站资源均来自网络或者用户投稿，仅供用于学习和交流：如有侵权联系删除!
温馨提示：本文属于积分文章，需要充值获得积分或升级VIP会员，也可在会员中心投稿获取。

神秘礼物描述 Peter为了祝他的澳大利亚朋友生日快乐，想要给他寄了一张贺卡。为了让礼物更有神秘感，他决定做一个“套娃信封”。所谓的“套娃信封”是指：假设贺卡的宽度和高度分别为 w 和 h，为了将

目录

题目信息

题目题干

答案解析

相关题目

提示声明

猜你喜欢

©2016-2021 100150.com

帮助中心

神秘礼物描述 Peter为了祝他的澳大利亚朋友生日快乐，想要给他寄了一张贺卡。为了让礼物更有神秘感，他决定做一个“套娃信封”。 所谓的“套娃信封”是指：假设贺卡的宽度和高度分别为 w 和 h，为了将

目录

题目信息

题目题干

答案解析

相关题目

提示声明

猜你喜欢

©2016-2021 100150.com

帮助中心

神秘礼物描述 Peter为了祝他的澳大利亚朋友生日快乐，想要给他寄了一张贺卡。为了让礼物更有神秘感，他决定做一个“套娃信封”。所谓的“套娃信封”是指：假设贺卡的宽度和高度分别为 w 和 h，为了将