摘要：生日禮物題目來源京東實習生招聘原題鏈接可在線提交賽碼網題目描述的生日快到了，這一次，小東決定為送一份特別的生日禮物為其慶生。小東計劃送一個生日卡片，并通過特別的包裝讓永遠難忘。

最近2個月時間都比較忙，另外還有些其他的事情，幾乎沒有怎么做題和寫文章了，害怕自己又開始懶散起來了，所以還是督促自己不斷地學習和練習編碼。最近還需要好好學下python面向對象的一些知識了。
今天我們來分析一個JD的2016實習生招聘題目，該題目在賽碼網上標為5星難度，我認為這個題目的難點在于對題目的理解，并且如何在較短的時間內選擇一個更佳的算法來完成coding。

<題目來源： 京東2016實習生招聘 原題鏈接-可在線提交(賽碼網)>

BF的生日快到了，這一次，小東決定為BF送一份特別的生日禮物為其慶生。作為高智商中的佼佼者，BF在國外求學，因此小東無法與之一起慶生。小東計劃送一個生日卡片，并通過特別的包裝讓BF永遠難忘。
她決定把卡片套裝在一系列的信封A?=?{a1,??a2,??...,??an}中。小東已經從商店中購買了很多的信封，她希望能夠用手頭中盡可能多的信封包裝卡片。為防止卡片或信封被損壞，只有長寬較小的信封能夠裝入大些的信封，同尺寸的信封不能套裝，卡片和信封都不能折疊。
小東計算了郵寄的時間，發現她的時間已經不夠了，為此找你幫忙包裝，你能幫她嗎？

首先根據樣例確認題目要求。
這里我再給出一組樣例數據并且給出正確輸出來驗證是否徹底理解題目要求：
5 1000 998
5002 5005
5003 5004
5003 5002
5002 5001
5002 5002
正確的輸出是
2
4
2

注意到以下3個問題：
(1)題目要求的卡片必須是裝入能裝入且最小的一個信封
(2)如果有多個信封可以選擇，那么選擇先拿到手上的，也就是在樣例中先出現的封信，具體可以參見我給出的那組樣例輸出，最后選擇了2而不是3，就是以為在2，3都可用時，選擇先出現的，也就是第2個封信
(3)信封不能旋轉，但是這點似乎題目中并沒有提及到

現在我們來討論如何解決這個問題
由于信封要被一層一層的封裝，并且要用到盡可能多的信封。得到的解如果是r[1], r[2], ... r[n]，那么滿足r[i] < r[i + 1] ("<"表示左側可以被右側裝下)，這有什么用呢？這提示我們需要對其進行一個整理，得到一個整理后的序列滿足：
envelop[1], envelop[2], ... envelop[i], ... envelop[n]
envelop[j] !> envelop[i] (i > j) 其中("!>" 表示左側能不右側裝下信封，>表示左側可以裝下右側信封)
這樣的話，我們可以考慮使用面積進行排序。因此面積大的不一定的下面積小的信封，但是面積小的一定裝不下面積大的信封 。

在得到這樣的一個具體拓撲關系(關于拓撲排序/結構，可以參考相關資料)序列之后，如果你對動態規劃(DP)有所了解，似乎首先會想到最長不下降子序列(LIS)問題，因為在得到拓撲序列后，我們可以按這個序列來劃分階段，來進行動態規劃。

設f[i]表示，如果選擇i個信封來裝可以最多使用的信封個數，同時設g[i]記錄i的前一個使用的信封的下標。由于最后我們要輸出信封的順序編號，別忘記了帶上原來的順序編號，在拓撲排序的時候，我們可以在遇到多個入度為0的點時，優先選擇編號較小的點加入拓撲序列，方便后續DP時的處理。
f[i] = max(f[j]) + 1, i > j and f[j] > 0 and envelop[i] > envelop[j]
g[i] = j (f[J] = f[i], j = min{J})
特別注意的是，由于有多個信封可用時需要選擇編號較小的，計算g[i]時，當有多個f[j]都滿足條件時，選擇最小的那個j。
最后的答案是max(f[i])，最后一個選擇是信封是i最小的那個。然后我們根據g[i]可以倒推出所有選擇信封。

至此，問題得到了解決。

但是，我們再咨詢觀察得到的拓撲序列發現，當確定最開始的信封之后，如果envelop[i] < envelop[j]，并且j是第一個滿足這個條件的信封，顯然我們會選擇j，因為后面的信封只存在兩種情況，不能裝下j，但是都比較j晚出現，不會選擇。如果能把j裝下，且第一個出現，我們依然會選擇。反之，如果不按這個策略選擇，顯然不可能得到更好的解。
簡單反證如下(如果用數學歸納法也類似):
現在有序列envelop[] 其中envelop[0]是最小能裝入卡片的信封，envelop[i]是第一個可以裝下envelop[0]的信封，假設選擇envelopj得到更優的解，那么存在兩種情況：
1) envelop[j] > envelop[i]，這時加入envelop[i]顯然可以使用多一個信封，與假設矛盾
2) envelop[j] !> envelop[j]，選擇更早出現的i才符合題目要求，與假設矛盾

一些后話：
1.這個題目不一定每個人都會立刻想到使用類似LIS的算法，比如不會LIS，又比如一眼就能看出問題本質，使用更佳的解法。更多時候我們可能是一步一步進行算法的演進，然后再不斷的進行更好的選擇和優化。問題可以有多種正確解法，但是并不是每種正確解法都是最優的。

2.關于拓撲排序的方式有多種，我這里并沒有使用基于圖的方法，因為需要建圖(O(n^2))在時間上相對我直接使用O(n^2)的插入排序的方法并沒有優勢。
具體實現的時候，我每次在原來的信封序列中取一個，放在已經得到的拓撲序列封信序列的第一個位置，然后和后一個比較，看是否需要交換，如果交換后，繼續向后比較，不需要交換則比較結束，繼續這個過程知道原來的信封已經取完
envelop a和envelop b交換的條件是：
envelop a > envelop b
or
envelop a !> envelop b and envelop a !< envelop b and Pa > Pb
其中Pa > Pb表示a在原給出的信封序列中位置更靠后

3.最后，在參考其他答案的時候，我也發現了一個O(nlogn)的算法，算法思想和我們提到的大致相同，他首選是按面積進行一個排序，然后僅通過O(n)的一次掃描就得到最后的答案，思想比較巧妙。有興趣可以在題目鏈接的“正確答案”中查看。

4.此外，關于LIS算法以及優化可以參考以下文章:
http://blog.csdn.net/hulifang...
http://blog.csdn.net/wall_f/a...

import sys

const_w = 0
const_h = 1
const_p = 2


def is_swap(a, b):
    a_contain_b = True if a[const_w] > b[const_w] and a[const_h] > b[const_h] else False
    b_contain_a = True if a[const_w] < b[const_w] and a[const_h] < b[const_h] else False

    if a_contain_b or (not a_contain_b and not b_contain_a and a[const_p] > b[const_p]):
        return True
    return False


def sort(envelops):
    s_envelops = []
    for envelop in envelops:
        s_envelops.insert(0, envelop)
        for i in range(len(s_envelops) - 1):
            if is_swap(s_envelops[i], s_envelops[i + 1]):
                temp = s_envelops[i]
                s_envelops[i] = s_envelops[i + 1]
                s_envelops[i + 1] = temp
            else:
                break
    return s_envelops


def main():
    envelops = []

    while True:
        line = map(int, sys.stdin.readline().strip().split())
        if len(line) < 3:
            return

        n, w, h = line[0], line[1], line[2]

        for i in range(n):
            line = map(int, sys.stdin.readline().strip().split())
            envelops.append((line[0], line[1], i + 1))
        s_envelops = sort(envelops)

        card_in = -1
        min_area = sys.maxint
        for i, s_envelop in enumerate(s_envelops):
            if s_envelop[const_w] > w and s_envelop[const_h] > h and s_envelop[const_w] * s_envelop[const_h] < min_area:
                min_area = s_envelop[const_w] * s_envelop[const_h]
                card_in = i

        if card_in < 0:
            print 0
        else:
            cnt = 1
            results = [s_envelops[card_in][const_p]]
            last = s_envelops[card_in]
            for i in range(card_in + 1, n):
                if s_envelops[i][const_w] > last[const_w] and s_envelops[i][const_h] > last[const_h]:
                    cnt += 1
                    results.append(s_envelops[i][const_p])
                    last = s_envelops[i]

            print cnt
            for result in results:
                print result,
            print

        envelops[:] = []


        # for s_envelop in s_envelops:
        #     print s_envelop[const_w], s_envelop[const_h], s_envelop[const_p]


if __name__ == "__main__":
    main()