題目鏈接

題目

Mark下大神的博客：http://morris821028.github.io/ 簡直太強(qiáng)了。 題解鏈接：http://morris821028.github.io/2014/10/03/oj/uva/uva-12166/#PRoblem

題目大意：

給一個(gè)天平表達(dá)式，請問至少要調(diào)整幾個(gè)權(quán)重才能使之平衡。（直接復(fù)制來的）

解題過程：

自己大概廢了一個(gè)小時(shí)想一個(gè)特麻煩的解法，首先想的是自頂向下的平衡，然后dfs下去還是從必須從葉節(jié)點(diǎn)開始平衡。

于是想自底向上平衡，每次把可以平衡成的質(zhì)量和調(diào)整的次數(shù)傳給上一層，比如調(diào)整[1,2]，給上一層傳遞三個(gè)狀態(tài)：調(diào)整2到1，質(zhì)量變?yōu)?，調(diào)整1次；調(diào)整1變?yōu)?，質(zhì)量變?yōu)?，調(diào)整一次；兩個(gè)都一起調(diào)整到一個(gè)任意的數(shù)，調(diào)整兩次。 顯然這樣需要給每個(gè)節(jié)點(diǎn)開辟一個(gè)空間儲(chǔ)存狀態(tài)，妥妥爆內(nèi)存。

想了一個(gè)小時(shí)只是這個(gè)結(jié)果，于是去百度了下，看到： 那麼可以得知道假使一個(gè)權(quán)重不改，最後的天平重量為何。 假使 depth 上的權(quán)重 w 不改，則最後的天平重量就是 w * pow(2, depth)。

于是想到建樹，統(tǒng)計(jì)下葉子節(jié)點(diǎn)所在的層數(shù)，然后拿每個(gè)葉子節(jié)點(diǎn)跑一邊，結(jié)果是O(n^2)。

后來看到這個(gè)博客確實(shí)是驚艷到了……

題目分析：

這里分析下下面的代碼好了。

這里map的使用和遍歷可以做模板了，要是我的話，就桶排然后遍歷一遍了…

這個(gè)遞歸寫的真是太強(qiáng)了！！

然后就是sscanf的用法，可以拿來做模板，要我的話，專門寫一個(gè)字符串轉(zhuǎn)整數(shù)的函數(shù)了，麻煩的要死。

AC代碼：