Uvalive – 4621 CAV greed + analysis "suggestions collection"

Hello everyone , I meet you again , I'm the king of the whole stack .

The main idea of the topic ： There's a map of the cave , To store water in this cave , The water is required not to touch the top of the cave . Now give the top position and ground height of each position . How much water can I put at most

Their thinking ： According to the laws of Physics , Every continuous section with water , The water level must be equal So we can calculate the height of water level in the same continuous interval , This water level is equal to the height of the top of the lowest cave . Based on this , Update from left to right , Then update from right to left , You can get the water level height of each position

#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 1000010;
const int INF = 0x3f3f3f3f;
int s[N], p[N], n;

void init() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &p[i]);
    }

    for(int i = 0; i < n; i++) {
        scanf("%d", &s[i]);
    }
}

int solve() {
    int t = INF;
    for(int i = 0; i < n; i++) {
        t = min(t, s[i]);
        t = max(t, p[i]);

        s[i] = t;
    }

    t = INF;
    for(int i = n - 1; i >= 0; i--) {
        t = min(t, s[i]);
        t = max(t, p[i]);

        s[i] = t;
    }

    int ans = 0;
    for(int i = 0; i < n; i++)
        ans += s[i] - p[i];

    return ans;
}

int main() {
    int test;
    scanf("%d", &test);
    while(test--) {
        init();
        printf("%d\n", solve());
    }
    return 0;
}

Copy

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/116603.html Link to the original text ：https://javaforall.cn