等价转换与其说是一种算法的设计方法,更不说是一种算法思想。这种思想能有助于我们把复杂的问题简单化,帮我们理清问题的思路,甚至能直接得出求解问题的方法。
下面通过一道具体的题目来像读者介绍这种思想。
Gergovia酒的交易(11054年葡萄酒Gergovia交易,UVa)
直线上有n (2 & lt;=n<=100000)个等距离的村庄,每个村庄要么买酒,要么卖酒。设第i个村庄对酒的需求为ai (-1000 & lt;=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;
而(cin>祝辞n&, n) {
长长的ans=0,,=0;
for (int i=0; i祝辞;人工智能;
ans +=abs(去年);
去年+=;
}
cout<& lt; ans<& lt;“\ n”;
}
返回0;
}
此篇博客,希望读者能对“等价转换”的思想有所了解。由于小编水平有限,欢迎读者指正。 
