洛谷P9485积水 题解

Genshin___Player · 2023-08-14 18:55:17 · 个人记录

——1.题目链接 来自原神的礼物

思路

prt1: 求总积水量

看到题面，我们首先想到模拟，对于每个高度算出它能贡献多少积水 然后我们画一张简图便可以发现：对于每一个i，它上面积的水等于他左边最大高度与右边最大高度的最小值减去他的高度（图解显而易见） 这样我们便可以开两个前缀/后缀最大值数组维护每个点能积的水，算出总水量，问题便解决了三分之一！

prt2：求改变后的积水最少值

不难想到有两种改法，第一种对水池中的柱子加高，便可以得到ans=max(maxl , maxr) - h[i]的水减少量，这个我们只需要在求总水量时跟着一起维护即可 第二种便是降低边界水池的高度让它里面的水流出去，我们可以分别从左右两边开始讨论，画图可以知道，左边界能降到的最低高度为maxl[l - 1]，高于低于 此值都会错失最优情况，我们便记low = maxl[l - 1],从左往右开始模拟，对每个枚举到的点i(需保证a[i] < a[l])看其w值(同上)是否大于max(low , a[r]) 若大于则可降低高度贡献答案，需要注意的是low值也需动态更新，当结束对从左开始每一个区间的答案计算时便更新ans值取最大值即可，从右往左同理

至此，此题解毕

code

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
typedef long long ll;
ll maxl[maxn] , maxr[maxn] , a[maxn] , deep , ans , n;
int main()
{
    int T;
    scanf("%d" , &T);
    while(T--)
    {
        scanf("%lld" , &n);
        ans = deep = 0;
        maxr[n + 1] = 0;
        maxl[0] = 0;
        for(int i = 1; i <= n; i++)
        {
            scanf("%lld" , &a[i]);
        }
        for(int i = 1; i <= n; i++)maxl[i] = max(maxl[i - 1] , a[i]);
        for(int i = n; i ; i--)maxr[i] = max(maxr[i + 1] , a[i]);
        for(int i = 1; i <= n; i++)
        {
            ll w = min(maxl[i - 1] , maxr[i + 1]);
            if(w > a[i])
            {
                ans += w - a[i];
                deep = max(w - a[i] , deep);
            }
        }
        ll l = 1 , r = 2;
        while(r <= n)
        {
            ll cnt = 0 , low = maxl[l - 1];
            while(a[r] < a[l])
            {
                ll w = min(maxl[r - 1] , maxr[r + 1]);
                if(w > max(low , a[r]))cnt += w - max(low , a[r]);
                low = max(low , a[r]);
                r++;
                if(r == n + 1)break;
            }
            deep = max(deep , cnt);
            l = r; r++;
        }
        l = n - 1, r = n;
        while(l >= 1)
        {
            ll cnt = 0 , low = maxr[r + 1];
            while(a[l] < a[r])
            {
                ll w = min(maxl[l - 1] , maxr[l + 1]);
                if(w > max(low , a[l]))cnt += w - max(low , a[l]);
                low = max(low , a[l]);
                l--;
                if(l == 0)break;
            }
            deep = max(deep , cnt);
            r = l;
            l--;
        }
        printf("%lld\n" , ans - deep);
    }
    return 0;
}