|
The Wedding Juicer
Description
Farmer John's cows have taken a side job designing interesting punch-bowl designs. The designs are created as follows:
The blocks are all glued together carefully so that punch will not drain through them. They are glued so well, in fact, that the corner blocks really don't matter! FJ's cows can never figure out, however, just how much punch their bowl designs will hold. Presuming the bowl is freestanding (i.e., no special walls around the bowl), calculate how much juice the bowl can hold. Some juice bowls, of course, leak out all the juice on the edges and will hold 0. Input
* Line 1: Two space-separated integers, W and H
* Lines 2..H+1: Line i+1 contains row i of bowl heights: W space-separated integers each of which represents the height B of a square in the bowl. The first integer is the height of column 1, the second integers is the height of column 2, and so on. Output
* Line 1: A single integer that is the number of cc's the described bowl will hold.
Sample Input 4 5 5 8 7 7 5 2 1 5 7 1 7 1 8 9 6 9 9 8 9 9 Sample Output 12 Hint
OUTPUT DETAILS:
Fill-up the two squares of height 1 to height 5, for 4 cc for each square. Fill the square of height 2 to height 5, for 3 cc of joice. Fill the square of height 6 to height 7 for 1 cc of juice. 2*4 + 3 + 1 = 12. Source |
题目大意：有一个大酒杯，是一个W×H的矩形，矩形的每个格子的高度给出，酒杯的边缘被视作高度为0（话说这还是酒杯吗
），求这个酒杯里最多能盛的果汁的体积。
这题很好地体现了木桶原理，即一个木桶的装水量取决于最短的那块木板。
首先把边界的元素放入一个小根堆，然后每次从堆中取出最小的那个元素，从那个元素向四周的没有访问过的元素扩展，如果新的元素比该元素高，就直接放入堆中，否则把答案递增新元素和当前元素的高度差，再把新元素的高度改成当前元素的高度，最后把该元素放入堆。
小根堆可以用STL中的优先队列，虽然慢一些，但代码短很多。
代码在此。
评论 (0)
