POJ 3658 / P2897 [USACO08JAN]人工湖Artificial Lake（模拟）

ArtificialLake

Time Limit: 3000MS	Memory Limit: 65536K
Total Submissions: 2119	Accepted: 710

Description

The oppressively hot summer days have raised the cows' clamoringto its highest level. Farmer John has finally decided to build an artificiallake. For his engineering studies, he is modeling the lake as a two-dimensionallandscape consisting of a contiguous sequence of N soon-to-be-submerged levels (1 ≤ N ≤ 100,000) conveniently numbered 1..N from left to right.

Each level i is described by two integers, itswidth W_i (1 ≤ W_i ≤ 1,000) and height (like a relativeelevation) H_i (1 ≤ H_i ≤ 1,000,000). The heights of FJ'slevels are unique. An infinitely tall barrier encloses the lake's model on theleft 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 flowingwater into the bottom of the lowest elevation at a rate of 1 square unit ofwater 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 allgood models, assume that falling and flowing happen instantly. Determine thetime 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.

Input

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

Output

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

SampleInput

3

4 2

2 7

6 4

SampleOutput

4

50

26

 

Source

​​USACO 2008 January Gold​​ 

算法分析：

题意：向N个连续且高度不同的平台灌水，平台各有宽度，且高度各不相同。一开始，先向高度最低的平台灌水，直到灌满溢出，流向其他的平台，直至所有平台都被覆盖。已知每分钟注入高度为1且宽度为1的水，问每个平台恰好被高度为1的水覆盖的时间。

分析：

第一步：记录每个平台的高度宽度（h，w）和左右平台（l，r），先找到最低的平台，然后开始灌水。

第二步：灌满最低的平台后，水溢出，相当于该平台消失，更新左右平台，寻找下一流向哪个平台。

注意用long long 。

代码实现：

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<vector>
const long long  INF = 0x3f3f3f3f3f3f3f3f;
#define PI acos(-1.0)
#define N 100005
#define MOD 2520
#define E 1e-12
using namespace std;
struct node
{
   long long  w,h;
    int l,r;//左右平台标号
}a[N];
 int n;
 long long ans[N];
int find_lowest()//寻找一开始最低平台
{
    long long minn=INF,cur=0;
    for(int i=1;i<=n;i++)
        if(a[i].h<minn)
    {
        minn=a[i].h;
        cur=i;
    }
     return cur;
}
int update_lowest(int cur)//更新下一个流向的平台标号，此题关键部分
{
    while(1)
    {
        int l=a[cur].l,r=a[cur].r;
        if(a[l].h<a[cur].h) cur=l;
        else if(a[r].h<a[cur].h) cur=r;
        else return cur;
    }
}
int run(int cur)
{
    int cnt=1;//已经淹没平台个数
    long long  sum=0;
    while(cnt<=N)
    {
        cnt++;
       sum+=a[cur].w;//记录答案
       ans[cur]=sum;
       int l=a[cur].l,r=a[cur].r;
       sum+=(min(a[l].h,a[r].h)-a[cur].h-1)*a[cur].w;//注意需要-1，因为一开始先加了一层

       a[l].r=r;//中间被淹没，更新左右编号
       a[r].l=l;
       if(a[l].h<a[r].h)//更新宽度
       {
           a[l].w+=a[cur].w;
           cur=l;
       }
       else
       {
           a[r].w+=a[cur].w;
           cur=r;
       }
       cur=update_lowest(cur);//流向下一个平台，不一定是左右平台
    }
    return 0;
}
int main()
{

    while(scanf("%d",&n)!=EOF)
    {
      for(int i=1;i<=n;i++)
        scanf("%lld%lld",&a[i].w,&a[i].h);
       for(int i=0;i<=n+1;i++)//初始化每一个平台的左右平台
        {
         a[i].l=i-1;
         a[i].r=i+1;
        }
        a[0].w=a[n+1].w=1;   //两边宽度设为无限高
        a[0].h=a[n+1].h=INF;//两边高度设为无限高

        int cur=find_lowest();
        run(cur);
        for(int i=1;i<=n;i++)
            printf("%lld\n",ans[i]);
    }
    return 0;
}