题解：P2897 [USACO08JAN] Artificial Lake G

_EternalRegrets_ · 2024-08-23 23:38:38 · 题解

P2897 题解

题意描述：

有一个人工湖，它可以被划分为 n 个平台，已知平台的高度和宽度。 从人工湖的最低平台上方开始注水，水会自然流动（假设瞬间流动）。 求各个平台被覆盖（被浸没至少 1 单位高度）的时间。

Solution:

这里可以使用链表，将相邻的平台链接起来。（链表可以表示左右的关系）

当一个平台被注水，使得与两侧的某一个平台水平（没有同样高度的平台），它们就可以被视为一个大平台。

具体实现方法见代码中注释。

code:

#include<bits/stdc++.h>
#define int long long
using namespace std;

struct node{
    int w,h,l,r;
};

node a[100005];
int ans[100005];

signed main(){
    int n; cin>>n;

    int k; k=-1; //寻找最低点；k指的是现在向最低点注水时，相当于向编号为k的平台注水（因为流动）
    for(int i=1;i<=n;i++){
        cin>>a[i].w>>a[i].h;
        a[i].l=i-1,a[i].r=i+1;

        if(k==-1 || a[k].h>a[i].h){
            k=i;
        }
    }

    a[0].h=a[n+1].h=LLONG_MAX; //两侧的墙壁
    int now; now=0; //时间

    while(a[k].l!=0 || a[k].r!=n+1){
        if(a[k].h>a[a[k].l].h){
            k=a[k].l;
            continue;
        } //如果左侧墙壁比现在的高度要更低，则转移到左侧（此时右侧不可能也比现在的高度低）

        if(a[k].h>a[a[k].r].h){
            k=a[k].r;
            continue;
        } //同上，但是对称

        //现在两侧均比现在个高度高
        int nowh; nowh=min(a[a[k].l].h,a[a[k].r].h)-a[k].h;
        ans[k]=now+a[k].w;
        //找到左右边哪个更低，nowh是需要填的高度
        now+=a[k].w*nowh;
    //填充到左右较低侧的高度

//----------------------------------------接链表
        a[a[k].r].l=a[k].l;
        a[a[k].l].r=a[k].r;

        if(a[a[k].l].h>a[a[k].r].h){
            a[a[k].r].w+=a[k].w; //可以视为一个大平台
            k=a[k].r;
        }
        else{ //题目中说明高度不可能相同
            a[a[k].l].w+=a[k].w; //同上
            k=a[k].l;
        }
    }
//----------------------------------------
    ans[k]=now+a[k].w; //补上最后一层 （此时 a[k].w 等于人工湖的总宽度）

    for(int i=1;i<=n;i++){
        cout<<ans[i]<<endl; 
    }

    return 0; //完结撒花！
}