题目描述

The oppressively hot summer days have raised the cows' clamoring to its highest level. Farmer John has finally decided to build an artificial lake. For his engineering studies, he is modeling the lake as a two-dimensional landscape consisting of a contiguous sequence of N soon-to-be-submerged levels () conveniently numbered 1..N from left to right.
Each level i is described by two integers, its width and height (like a relative elevation) . The heights of FJ's levels are unique. An infinitely tall barrier encloses the lake's model on the left and right. One example lake profile is shown below.
         *             *  :
         *             *  :
         *             *  8
         *    ***      *  7
         *    ***      *  6
         *    ***      *  5
         *    **********  4 <- height
         *    **********  3
         ***************  2
         ***************  1
Level    |  1 |2|  3   |

In FJ's model, he starts filling his lake at sunrise by flowing water into the bottom of the lowest elevation at a rate of 1 square unit of water per minute. The water falls directly downward until it hits something, and then it flows and spreads as room-temperature water always does.  As in all good models, assume that falling and flowing happen instantly. Determine the time at which each elevation's becomes submerged by a single unit of water.
     WATER              WATER OVERFLOWS                     
       |                       |                           
     * |          *      *     |      *      *            *
     * V          *      *     V      *      *            *
     *            *      *    ....    *      *~~~~~~~~~~~~*
     *    **      *      *~~~~** :    *      *~~~~**~~~~~~*
     *    **      *      *~~~~** :    *      *~~~~**~~~~~~*
     *    **      *      *~~~~**~~~~~~*      *~~~~**~~~~~~*
     *    *********      *~~~~*********      *~~~~*********
     *~~~~*********      *~~~~*********      *~~~~*********
     **************      **************      **************
     **************      **************      **************

     After 4 mins        After 26 mins       After 50 mins
     Lvl 1 submerged     Lvl 3 submerged     Lvl 2 submerged

Warning: The answer will not always fit in 32 bits.

输入描述:

* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 describes level i with two space-separated integers:  and 
    

输出描述:

* Lines 1..N: Line i contains a single integer that is the number of minutes that since sunrise when level #i is covered by water of height 1.

示例1

输入
3
4 2
2 7
6 4
输出
4
50
26
说明
Three levels just as in the example above. Water will fill the first level because it is the lowest.
As in the illustrations above.

解答

题意:给出N个连续的平台，他们各有宽度，且高度不同。先向高度最低的平台灌水，直到灌满溢出，流向其他的平台，直至所有平台都被覆盖。已知每分钟注入高为1宽为1的水，求每个平台恰好被高为1的水覆盖的时间。
思路:先找到最低的平台，然后开始灌水。然后将最低的填满以后水溢出，相当于该平台消失，更新左右平台，寻找下一流向哪个平台，每次找最近的最低的平台h，然后将水填到h高度。向外扩展的时候，有时会遇到高度递减的情况，这时并不能填水，但要把这些高度都记录进栈，然后遇到一个比水面高的平台h时，模拟倒水，水会挨个淹没最低的平台，即需要从栈顶一个一个出栈计算淹没时间，直至栈顶平台高度>h，此时h入栈。重复执行就可算出答案。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int inf = 0x3f3f3f3f;
struct edge {
    int h, id;
    long long w;
}sp[MAXN], stp[MAXN];
long long cnt[MAXN];
int main() {
    int n, j, top, min_ = inf;;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        sp[i].id = i;
        scanf("%lld%d", &sp[i].w, &sp[i].h);
        if (min_ > sp[i].h)
            min_ = sp[j = i].h;
    }
    top = 0;
    sp[0].h = sp[n + 1].h = inf;
    stp[top] = sp[0];
    stp[++top] = sp[j];
    long long t = 0;
    int l = j, r = j, p;
    for (int i = 1; i <= n; i++) {
        long long w = 0;
        if (sp[l - 1].h < sp[r + 1].h)
            p = --l;
        else p = ++r;
        while (sp[p].h > stp[top].h) {
            stp[top].w += w;
            cnt[stp[top].id] = t + stp[top].w;
            t += (min(sp[p].h, stp[top - 1].h) - stp[top].h) * stp[top].w;
            w = stp[top].w;
            top--;
        }
        sp[p].w += w;
        stp[++top] = sp[p];
    }
    for (int i = 1; i <= n; i++)
        printf("%lld\n", cnt[i]);
    return 0;
}



来源：子夜葵