三分 --- CSU 1548: Design road Design road Problem's Link: http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1548

Mean: 

目的：从(0,0)到达(x,y)。但是在0~x之间有n条平行于y轴的河，每条河位于xi处，无限长，wi宽，并分别给出了建立路和桥每公里的单价

求：到达目标的最小费用。

analyse:

比赛的时候一直没想到思路，第二个样列怎么算都算不对，赛后才知道是三分。

首先把所有的桥移到最右端，然后三分枚举路和河的交点。

Time complexity: O(logn)

Source code: 

View Code