算法设计与优化之等价转换
更新:HHH   时间:2023-1-7


等价转换与其说是一种算法的设计方法,更不说是一种算法思想。这种思想能有助于我们把复杂的问题简单化,帮我们理清问题的思路,甚至能直接得出求解问题的方法。
下面通过一道具体的题目来像读者介绍这种思想。
Gergovia酒的交易(Wine trading in Gergovia,UVa 11054)
直线上有n(2<=n<=100000)个等距离的村庄,每个村庄要么买酒,要么卖酒。设第i个村庄对酒的需求为ai(-1000<=ai<=1000),其中ai>0表示要卖酒,反之表示要卖酒。所有村庄供需平衡,即所有的ai和为0.把第K个单位的酒从一个村庄运到相邻的村庄需要K个劳动力。请计算需要多少劳动力可以满足所有村庄的需求。
当我们读玩题目的时候似乎没有什么思路,觉得这么多的村庄似乎无法下手。下面小编带着读者来理清这道题的思路。我们从最左边的村庄开始考虑。如果它需要买酒,一定需要从村庄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;
    }
此篇博客,希望读者能对“等价转换”的思想有所了解。由于小编水平有限,欢迎读者指正。
返回编程语言教程...