題意分析

給定一個右鍵菜單的情況，每一個菜單內(nèi)選項的數(shù)量，以及其子菜單的選項情況。合理的安排整個菜單展開的最大長度最小，輸出這個最小值。

算法分析

題目中定義了菜單的元素：

row: 表示一行選項

section: 由至少一行row構(gòu)成，其中row的順序可以自由排列

panel: 由至少一個section構(gòu)成，其中section的順序可以自由排列

由于構(gòu)成panel的元素是固定的，所以一個panel的長度是固定的。所以影響其最大長度因素是該panel內(nèi)每行row的子菜單長度。

當(dāng)一行row所展開的子菜單超過該panel的長度時，就會導(dǎo)致整個菜單的總長度被拉長。如何合理的安排row的順序，使得被拉長的程度最小也就成了解決這道題的關(guān)鍵。

我們從只有從簡單的情況開始考慮。

panel只包含有1個section，section包含有?s?行row，記為R1..Rn，但是只有R1有子菜單，且長度為?r。

如果把R1放在第i行，則展開這個子菜單時的長度為?r+i-1?，所以總的長度為 max(?n?,?r+1-1?)。

因此得到我們的一個結(jié)論，有子菜單的row要盡可能往前放置。

panel只包含有1個section，section包含有?s?行row，記為R1..Rn，其中R1有長度為?r1?的子菜單，R2有長度為?r2?的子菜單，且?r1?≥?r2。

如果把R1放在第i行，R2放在第j行。則展開R1這個子菜單時的長度為?r1+i-1，展開R2這個子菜單時的長度為?r2+j-1。

方案一：i<j，表示R1放在R2前面，此時無法判定?r1+i-1?與?r2+j-1?的大小關(guān)系；

方案二：i>j，表示R2放在R1前面，此時一定有?r1+i-1?>?r2+j-1。

但是我們有?r1+i-1?≥ max(?r1+i-1?,?r2+j-1?)，所以方案一一定不差于方案二。

由此得到我們第二個結(jié)論，當(dāng)有多個包含子菜單的row時，要將子菜單長的盡可能放在前面。

panel只包含有2個section，記為S1,S2。

S1包含有?s1?行row，且展開這些row使得S1最少延伸到?sr1?行(即從S1的第?1?行開始計算，其展開的子菜單最長延伸到第?sr1?行)，令??1?=?sr1 - s1。舉個例子：

+-----------+
|?other?sec?|
+-----------+?????????????????-???-
|???S1?r1???|?????????????????^???^
+-----------+-----------+?????|???|
|???S1?r2??>|???????????|?????|???s1
+-----------+-----------+?????|???|
|???S1?r3???|???????????|????sr1??v
+-----------+-----------+?????|???-
|?other?sec?|???????????|?????|???|
+-----------+-----------+?????|????1
????????????|???????????|?????v???|
????????????+-----------+?????-???-

S2包含有?s2?行row，且展開這些row使得S2最少延伸到?sr2?行，令??2?=?sr2 - s2。

顯然有?sr1?≥?s1,?sr2?≥?s2。

對于S1和S2來說?s1，_s2_ 是它們的固有長度，它們對總長度的影響，是由??1?和??2?決定的。不妨假設(shè)??1?≥??2。

方案一：S1放在前面，S2放在后面。此時若將S1展開，會使得總長度增加??1-s2；展開S2，會使得總長度增加??2。無法判定??1-s2?與??2?的大小關(guān)系。

方案二：S2放在前面，S1放在后面。此時若將S1展開，會使得總長度增加??1；展開S2，會使得總長度增加??2-s1。因為??1?≥??2?>??2-s1?，所以結(jié)果為??1。

可以知道一定有??1?>??1-s2,??1?≥??2。因此方案一一定不差于方案二。

由此可以得到我們第三個結(jié)論，當(dāng)有多個section時，我們需要將???大的盡可能放在前面。

其中三個結(jié)論中，第二個結(jié)論實際上包含了第一個結(jié)論。而若將row看做只有1行row的section，第二結(jié)論其實也和第三個結(jié)論等價。所以得到精簡的結(jié)論：

對于row和section，我們要將子菜單長度與本體長度差值大的靠前放置。

由此我們可以得到對于panel的處理方法：

row：遞歸處理出每一個row的子菜單長度。

section: 將section內(nèi)的row進行排序，得到section的最優(yōu)長度方案，記錄其本體長度和子菜單長度。

panel：將panel內(nèi)的section進行排序，得到panel的最優(yōu)長度。

接下來我們來討論一下具體的實現(xiàn)。

首先可以肯定的是樹形結(jié)構(gòu)，下面以C++的代碼為例子，我們對三種元素分別建立結(jié)構(gòu)體：

struct?row?{
????int?childId;??????????//?子菜單指針
????int?expandLength;?????//?子菜單長度?
????row():childId(-1),expandLength(0)?{};
????row(int?_id):childId(_id),expandLength(0)?{};
};

struct?section?{
????vector<?row?>?rows;???//?包含的row情況
????int?selfLength;???????//?自身的長度?s1
????int?expandLength;?????//?展開子菜單之后的長度?sr1
????int?delta;????????????//?子菜單之后的長度與自身的差值??
????section():selfLength(0),expandLength(0),delta(0)?{};
};

struct?panel?{
????vector<?section?>?sections;?//?包含的section情況
????vector<?int?>?rowIds;???????//?讀入時該panel內(nèi)的rowId
};

讀入數(shù)據(jù)時，我們先將所有row都讀入：

panel?panels[?MAXN?];

//?讀入每一個panel的情況
int?n;
cin?>>?n;
int?id,?numOfIds;
for?(int?i?=?0;?i?>?numOfIds;
????while?(numOfIds--)?{
????????cin?>>?id;
????????if?(id?==?0)?++numOfIds;
????????panels[i].rowIds.push_back(id);
????}
????dealPanel(?panels[i]?);????//?處理panel的情況
}

其中dealPanel函數(shù)為：

void?dealPanel(panel?&p)?{
????if?(?(int)?p.rowIds.size()?==?0?)?return?;

????p.sections.push_back(section());
????int?sectionId?=?0;

????//?加入一個末尾0，方便處理最后一個section
????p.rowIds.push_back(0);

????//?依次出每一個section
????for?(int?i?=?0;?i?!=?(int)?p.rowIds.size();?++i)
????????if?(p.rowIds[i]?!=?0)?{
????????????p.sections[?sectionId?].rows.push_back(?row(p.rowIds[i])?);
????????}???else?{
????????????//?新的section
????????????p.sections.push_back(section());
????????????sectionId++;
????????}
????return?;
}

根據(jù)我們的上面總結(jié)的處理方法，我們可以寫出對panel的處理函數(shù)：

bool?sortByExpandLength(row?x,?row?y)?{
????return?x.expandLength?>?y.expandLength;
}

bool?sortByDelta(section?x,?section?y)?{
????return?x.delta?>?y.delta;
}

int?getExpandLength(panel?&p)
{

????//?ret初始化為0，ret表示該panel的最小展開長度
????int?ret?=?0;

????//?枚舉每一個section
????for?(int?i?=?0;?i?!=?(int)?p.sections.size();?++i)
????{

????????//?處理該section內(nèi)的每一個row的子菜單
????????for?(int?j?=?0;?j?!=?(int)?p.sections[i].rows.size();?++j)
????????????p.sections[i].rows[j].expandLength?=?getExpandLength(?panels[?p.sections[i].rows[j].childId?]?);

????????//?根據(jù)row的expandLength對section內(nèi)的row進行排序
????????sort(p.sections[i].rows.begin(),?p.sections[i].rows.end(),?sortByExpandLength);

????????//?處理得到section的值
????????p.sections[i].selfLength?=?(int)?p.sections[i].rows.size();
????????p.sections[i].expandLength?=?p.sections[i].selfLength;?//?展開值至少為selfLength

????????//?枚舉每一個row，找到展開值最大的作為section的展開值
????????for?(int?j?=?0;?j?!=?(int)?p.sections[i].rows.size();?++j)
????????????if?(p.sections[i].expandLength?<?j?+?p.sections[i].rows[j].expandLength)
????????????????p.sections[i].expandLength?=?j?+?p.sections[i].rows[j].expandLength;

????????//?計算section的?值
????????p.sections[i].delta?=?p.sections[i].expandLength?-?p.sections[i].selfLength;

????????//?累加panel內(nèi)所有的row行數(shù)作為最小的ret
????????ret?+=?p.sections[i].selfLength;
????}

????//?根據(jù)section的?值進行排序
????sort(p.sections.begin(),?p.sections.end(),?sortByDelta);

????//?now記錄當(dāng)前section的起始行數(shù)
????int?now?=?0;

????//?枚舉每一個section，找到展開值最大的作為panel的展開值
????for?(int?i?=?0;?i?!=?(int)?p.sections.size();?++i)
????{
????????if?(ret?<?now?+?p.sections[i].expandLength)
????????????ret?=?now?+?p.sections[i].expandLength;

????????//?累加為下一個section的起始行數(shù)
????????now?+=?p.sections[i].selfLength;
????}

????return?ret;
}

最后我們的答案只需要：

cout?<<?getExpandLength(?panels[0]?)?<<?endl;

該段代碼還可以以進一步優(yōu)化，將其中的dealPanel和getExpandLength還可以再合并為一個函數(shù)的。