打包礼物
Description:
有k个礼物,如果两个礼物的体积满足小礼物的体积的两倍不超过大礼物的体积,那么小礼物可塞在大礼物里。同时**一个大礼物里最多只能塞一个其他小礼物,小礼物里可包含其他更小的礼物。如果小礼物被塞进大礼物里了,那么就不用再付小礼物的快递费了。如何使得最后剩下的礼物数量最少?
Input:
输入第一行有一个正整数 n,表示礼物的数量;
接下来一行共 n 个正整数,依次表示这些礼物的体积 V ;
Output
第一行输出一个正整数 p,表示安排后剩下的最少礼物数量。
接下来 p 行,每行开头输入一个正整数 t,表示这个礼物里被塞进去的礼物总数量。接下来输入 t 个数,从前到后依次表示这些礼物的编号,按照体积从小到大排序。
输入
1 | 5 |
输出
1 | 3 |
解析:
构造一个结构体,里边存的是编号,体积,和变量down(存下一个值)(初始化为-1)
按体积由小到大进行排序,用两个变量i j从尾部向前遍历,先固定 i , 然后 j–, 如果 i 对应的礼物能包下 j 对应的礼物,让 i 的down 指向 j ,并给j 的down 赋-2 (以为包含)跳出内层循环,下次接着上次的 j -1 (思考)。重复这个过程直到结束 然后输出。