11368: Nested Dolls ★★★☆☆ 題組：Problem Set Archive with Online Judge 解題者：黃育成 解題日期：2018年5月31日 題意：首先會出現一數字n代表有n組測資。每組測資都會先給一個數字m代表會有m個俄羅斯娃娃(簡稱俄娃)，接著會給m個俄娃的寬與高。 把他們盡量合併，問最後露在外面的俄娃最少為多少個? (俄娃A只有在長寬皆比 B 大或小的時候兩個才可以合併為一個)
題意範例： Input: Output: 4 //4筆測資 3 //3個俄娃 1 20 30 40 50 30 40 4 //4筆測資 3 //3個俄娃 1 20 30 40 50 30 40 //(寬1 長1 寬2....) 做法: 排列: 40 50, 30 40, 20 30 拿出來排: 50 -> 50改40 -> 40改30 4 10 10 20 30 40 50 39 51 2 排列: 40 50, 39 51, 20 30, 10 10 拿出來排: 50 -> 51, 50-> 51, 50改30 -> 51, 30改10
6 //6個俄娃 4 1 1 2 7 3 5 3 6 4 7 5 4 做法: 排列: 5 4, 4 7, 3 4, 3 5, 2 7, 1 1 拿出來排:4 -> 4, 7-> 4 , 7改4 -> 4, 4, 5 -> 4, 4, 5, 7 -> 4改1, 4, 5, 7 CF: 排列: 5 4, 4 7, 3 5, 3 4, 2 7, 1 1 拿出來排:4 -> 4, 7 -> 4 , 7改5 -> 4, 5改4 -> 4, 4, 7 -> 4改1, 4 , 7 ->ANS:3 ，但 是錯的 ->5改4 代表3 4可以與3 5合併，但它們的寬是一樣高，所以 其實不能合併 ->同寬時先排小才排大可以避免他們不會合併在一起。 越後面越高，但要找比自己的合併，所以不會跟前面幾個合併。 3 3 10 10 10 10 10 10 做法: 拿出來排:10 -> 10, 10 (因為沒有比自己高)-> 10, 10, 10
解法： 首先 按照寬度由大到小排列，若寬一樣則依高度 “由小到大”排列。 接著一個一個拿出來合併，每一次都尋找“高度變數”比自己還高“一點點”(即最接近自己高度且比自己高)的那一串合併，並把該串俄娃的“高度變數”改為自己的高度。若自己已是最高的，則自己變成新的一串俄娃，且設“高度變數”為自己的高度。 依序做，最後串列的個數(有幾個 “高度變數”)即為答案。
討論： 時間複雜度: C++Sort->O(nlogn) 合併->O(n)(n筆資料) *O(logn) (尋找比自己高一點的值，使用set的 upper_bound() function) 總和:O(nlogn)