I have a problem which I don't really understand the solution.``↵
↵
``Give n buckets of water. The i_th bucket contains a_i liters of water. You can move water from bucket i to bucket i + 1.The cost when you move water is exactly the amount of water.Find the minimum cost you have to do that a_i <= a_i+1 <= ... <= a_n.``↵
↵
``The solution is quite easy to read,but I can't prove it right.First, you must create n + 1 points from the input, the coordinates are {0;0},{1;s_i},...,{n,s_n} with s_i is prefix sum of array a_i from 1 to i.After that,you run a loop from 0 to n-2.If 3 consecutive points is not counter clockwise(ccw for short), then you add the area of the triangle with peaks are these 3 points to the result.``↵
↵
Is this an application of convex hull,or is there any documents about this problem type ?``↵
↵
Thank you and apologize for my bad English. It's not my mother language.``
↵
``Give n buckets of water. The i_th bucket contains a_i liters of water. You can move water from bucket i to bucket i + 1.The cost when you move water is exactly the amount of water.Find the minimum cost you have to do that a_i <= a_i+1 <= ... <= a_n.``↵
↵
``The solution is quite easy to read,but I can't prove it right.First, you must create n + 1 points from the input, the coordinates are {0;0},{1;s_i},...,{n,s_n} with s_i is prefix sum of array a_i from 1 to i.After that,you run a loop from 0 to n-2.If 3 consecutive points is not counter clockwise(ccw for short), then you add the area of the triangle with peaks are these 3 points to the result.``↵
↵
Is this an application of convex hull,or is there any documents about this problem type ?
↵
Thank you and apologize for my bad English. It's not my mother language.
