題意分析
給定一個右鍵菜單的情況，每一個菜單內(nèi)選項(xiàng)的數(shù)量，以及其子菜單的選項(xiàng)情況。合理的安排整個菜單展開的最大長度最小，輸出這個最小值。
算法分析
題目中定義了菜單的元素：
row: 表示一行選項(xiàng)
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?行開始計(jì)算，其展開的子菜單最長延伸到第?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。因?yàn)??1?≥??2?>??2-s1?，所以結(jié)果為??1。
可以知道一定有??1?>??1-s2,??1?≥??2。因此方案一一定不差于方案二。
由此可以得到我們第三個結(jié)論，當(dāng)有多個section時，我們需要將???大的盡可能放在前面。
其中三個結(jié)論中，第二個結(jié)論實(shí)際上包含了第一個結(jié)論。而若將row看做只有1行row的section，第二結(jié)論其實(shí)也和第三個結(jié)論等價。所以得到精簡的結(jié)論：
對于row和section，我們要將子菜單長度與本體長度差值大的靠前放置。
由此我們可以得到對于panel的處理方法：
row：遞歸處理出每一個row的子菜單長度。
section:
將section內(nèi)的row進(jìn)行排序，得到section的最優(yōu)長度方案，記錄其本體長度和子菜單長度。
panel：將panel內(nèi)的section進(jìn)行排序，得到panel的最優(yōu)長度。
接下來我們來討論一下具體的實(shí)現(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進(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;?//?展開值至少為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;
????????//?計(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;
????//?枚舉每一個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;
該段代碼還可以以進(jìn)一步優(yōu)化，將其中的dealPanel和getExpandLength還可以再合并為一個函數(shù)的。
下載文檔
