[伯俊]BOJ 14719雨水JAVA

10278 ワード
アルゴリズム#アルゴリズム# テキストリンク
BOJ 14719雨水

質問する


2次元の世界には積み木がいっぱい積まれている.雨が降ると、積み木の間に雨が溜まります.

雨がひどく降った.水たまりの雨水の総量はいくらですか?

入力


第1行は、2次元世界の長手方向長さHおよび2次元世界の横方向長さWを与える.(1 ≤ H, W ≤ 500)
2行目では,積木高さを表す0以上H以下の整数が2次元世界の最左位置から順にW個与えられる.
したがって、ブロック内部に空きスペースがあることはできません.また,二次元世界の底は常に塞がれていると仮定できる.

しゅつりょく


2 Dワールドでは、1グリッドの容量は1です.積水の総量を出力する.
雨が全く積もらなければ、0を出力します.

サンプルI/O



ソースコード

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int H = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());

        int[] arr = new int[W];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int left = 0;
        int right = W - 1;

        int maxL = arr[left];
        int maxR = arr[right];

        int sum = 0;

        while (left != right) {
            int curL = arr[left];
            int curR = arr[right];

            maxL = Math.max(curL, maxL);
            maxR = Math.max(curR, maxR);

            if (maxL > maxR) {
                sum += maxR - curR;
                right--;
            } else {
                sum += maxL - curL;
                left++;
            }
        }
        System.out.println(sum);
    }
}

Comment


使用
  • ・투 포인터解除.
    • JavaScriptベース8
    マトリックスクラスバックアップ