🐷大肚肚
CF-4D普及+/提高

生日贺卡

1.0s💾 64MB

📋 题目描述

胖球肚手里有 nn 信封,编号从 11nn ,每个信封的宽度分别为 w1,w2,...,wnw_1,w_2,...,w_n ,每个信封的高度分别为 h1,h2,...,hnh_1,h_2,...,h_n ,现在她要用这些信封制作一条链,这条链上的信封的尺寸有严格要求,后一个信封的宽度和高度分别要严格大于前一个信封的宽度和高度,链条大小为该链条上信封的数量,她要在这条链条上的信封里装入朋友的生日贺卡,贺卡的宽度为 ww ,高度为 hh ,卡片的宽度和高度必须分别小于链条中最小信封的宽度和高度。注意,信封和卡片都不能进行旋转。你的任务是帮助胖球肚确定可以获得链条的最大长度。

📥 输入格式

第一行包含三个整数 nnwwhh1n50001 ≤ n ≤ 50001wh1061 ≤ w,h ≤ 10^6 )表示胖球肚拥有的信封数量以及卡片的宽度和高度。接下来的 nn 行,每行给出一个信封的大小,第 ii 个信封的信息包含两个整数 wiw_ihih_i 表示该信封的宽度和高度( 1wi,hi1061 ≤ w_i, h_i ≤ 10^6 )。

📤 输出格式

第一行仅有一个整数 mm 表示链条的最大长度,第二行给出最长链条上的 mm 个信封的编号( 两两之间用一个空格分隔 ),从编号最小信封的编号开始输出。如果最长的链不唯一,输出任何一个方案即可。如果 m=0m=0 则输出就没有第二行。

📝 样例 1

输入
2 1 1
2 2
2 2
输出
1
1

📝 样例 2

输入
3 3 3
5 4
12 11
9 8
输出
3
1 3 2

📚 来源

💡 题目讲解

1

理解题意

胖球肚过生日啦!她有 nn 个信封,每个信封有宽度 wiw_i高度 hih_i。她想把信封一个套一个,做成一条"信封链",送给朋友。

套信封的规则:后面那个信封的宽和高,都要严格大于前面那个(等于不行哦)。

就像俄罗斯套娃一样,小的放进大的里:

📮 第3个信封 (最大) ✉️ 第2个信封 💌 第1个信封 (最小) 🎂 生日贺卡

链条里最小的那个信封,还要能装下一张生日贺卡(贺卡宽 ww、高 hh,都要小于它的宽和高)。

🎯 我们要算:最长的"信封链"能有多长?并输出用了哪些信封的编号。

1 / 6