題意分析

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

算法分析

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

row: 表示一行選項(xiàng)

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

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

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

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

我們從只有從簡(jiǎn)單的情況開(kāi)始考慮。

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

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

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

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

如果把R1放在第i行，R2放在第j行。則展開(kāi)R1這個(gè)子菜單時(shí)的長(zhǎng)度為?r1+i-1，展開(kāi)R2這個(gè)子菜單時(shí)的長(zhǎng)度為?r2+j-1。

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

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

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

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

panel只包含有2個(gè)section，記為S1,S2。

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

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

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

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

對(duì)于S1和S2來(lái)說(shuō)?s1，_s2_ 是它們的固有長(zhǎng)度，它們對(duì)總長(zhǎng)度的影響，是由??1?和??2?決定的。不妨假設(shè)??1?≥??2。

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

方案二：S2放在前面，S1放在后面。此時(shí)若將S1展開(kāi)，會(huì)使得總長(zhǎng)度增加??1；展開(kāi)S2，會(huì)使得總長(zhǎng)度增加??2-s1。因?yàn)??1?≥??2?>??2-s1?，所以結(jié)果為??1。

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

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

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

對(duì)于row和section，我們要將子菜單長(zhǎng)度與本體長(zhǎng)度差值大的靠前放置。

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

row：遞歸處理出每一個(gè)row的子菜單長(zhǎng)度。

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

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

接下來(lái)我們來(lái)討論一下具體的實(shí)現(xiàn)。

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

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

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

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

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

panel?panels[?MAXN?];

//?讀入每一個(gè)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;

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

????//?依次出每一個(gè)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é)的處理方法，我們可以寫(xiě)出對(duì)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的最小展開(kāi)長(zhǎng)度
????int?ret?=?0;

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

????????//?處理該section內(nèi)的每一個(gè)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對(duì)section內(nèi)的row進(jìn)行排序
????????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;?//?展開(kāi)值至少為selfLength

????????//?枚舉每一個(gè)row，找到展開(kāi)值最大的作為section的展開(kāi)值
????????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;

????????//?計(jì)算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的?值進(jìn)行排序
????sort(p.sections.begin(),?p.sections.end(),?sortByDelta);

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

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

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

????return?ret;
}

最后我們的答案只需要：

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

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