題目鏈接

題目

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

題目大意：

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

解題過程：

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

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

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

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

后來看到這個博客確實是驚艷到了……

題目分析：

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

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

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

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

AC代碼：