溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

算法設(shè)計與優(yōu)化之等價轉(zhuǎn)換

發(fā)布時間：2020-07-26 18:31:03 來源：網(wǎng)絡(luò) 閱讀：557 作者：YXQiang 欄目：編程語言

等價轉(zhuǎn)換與其說是一種算法的設(shè)計方法，更不說是一種算法思想。這種思想能有助于我們把復(fù)雜的問題簡單化，幫我們理清問題的思路，甚至能直接得出求解問題的方法。
下面通過一道具體的題目來像讀者介紹這種思想。
Gergovia酒的交易（Wine trading in Gergovia，UVa 11054）
直線上有n(2<=n<=100000)個等距離的村莊，每個村莊要么買酒，要么賣酒。設(shè)第i個村莊對酒的需求為ai(-1000<=ai<=1000),其中ai>0表示要賣酒，反之表示要賣酒。所有村莊供需平衡，即所有的ai和為0.把第K個單位的酒從一個村莊運到相鄰的村莊需要K個勞動力。請計算需要多少勞動力可以滿足所有村莊的需求。
當(dāng)我們讀玩題目的時候似乎沒有什么思路，覺得這么多的村莊似乎無法下手。下面小編帶著讀者來理清這道題的思路。我們從最左邊的村莊開始考慮。如果它需要買酒，一定需要從村莊2往左運給它，而我們不需要考慮村莊2的酒是從哪里來的。（但是，我們可想而知，肯定要么是村莊2自己的酒，要么是村莊2右邊的村莊運到村莊2的）。這樣問題就等價于只有村莊2~n，且第2個村莊的需求為a1+a2。并且這個推理，不管ai<0，ai>0都是成立的。所以到這里，這道題的題目就理清了，理清以后似乎這道題簡答了好多，代碼也變得好寫一些了。
代碼如下


int main(){
        int n;
        while(cin>>n&&n){
                long long ans=0,a,last=0;
                for(int i=0;i<n;i++){
                        cin>>ai;
                        ans+=abs(last);
                        last+=a;
                    }
                    cout<<ans<<"\n";
            }
                return 0;
    }
此篇博客，希望讀者能對“等價轉(zhuǎn)換”的思想有所了解。由于小編水平有限，歡迎讀者指正。
向AI問一下細節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手