白峻14719雨水



マジシャンです


2次元の世界には積み木がいっぱい積まれている.雨が降ると、積み木の間に雨が溜まります.
雨がひどく降った.水たまりの雨水の総量はいくらですか?
アルゴリズムのヒントを見て、実装、シミュレーションと書いてあります.何でも書けば解ける.
最初に考えられる方法は,図のような2次元配列を探索する際に,ブロックとブロックの間の白空間の個数だけを数えることである.

1.1行をナビゲートするときに黒いブロックが表示された場合は、後からカウントします。


2.黒い塊の連続出現に対応


以上の2つの要因を考慮して,コードを記述した.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_14719_빗물 {
	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());
		boolean flag = false; //흰 블록을 세기위한 스위치 true면 셀 수 있다.
		int[] arr = new int[W];
		st = new StringTokenizer(br.readLine(), " ");
		int maxH = 0;
		for (int i = 0; i < W; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			maxH = Math.max(maxH, arr[i]);
			//주어진 블록들의 높이가 H보다 낮을수도 있으므로 최대 높이 블록 저장
		}
		int sum = 0;
        	//최대 높이 블록의 행 부터 검사 시작
		for (int i = H - maxH; i < H; i++) {
			int cnt = 0;
			flag = false;
            		for (int j = 0; j < W; j++) {
                    		//검정색 블록이라면 흰 블록 세야하므로 flag = true;
				//무조건 sum에 더해주고 nt는 0으로 초기화 
				if (i >= (H - arr[j])) {
					flag = true;
					sum += cnt;
					cnt = 0;
					continue;
				}
                		//flag가 true면 흰 블록 개수를 셀 수 있다.
				if (flag) 
					cnt++;
			}
		}
		System.out.println(sum);
	}
}
非常に簡単な解法です...次に、最大高さのブロックのローインデックスから開始し、時間を最大限に節約します.速度も136 msで思ったより速かったです.
第2の考え方は,最高ブロックの位置(maxh)に基づいて両側からmaxhにナビゲートし,同時に白空間を計算することである.

水が溜まるかどうかをチェックすればいいです。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_14719_빗물2 {
	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(), " ");
		int maxH = 0;
		int posi = 0;
		for (int i = 0; i < W; i++) {
			int s = Integer.parseInt(st.nextToken());
			if (maxH < s) {
				maxH = s;
				posi = i; // 가장 긴 블록의 길이와, 위치 저장
			}
            		arr[i] = s;
		}
		int sum = 0;
		int a = arr[0];//기준을 정해줌 
		int b = arr[W - 1];
		for (int i = 1; i < posi; i++) {
			if (a > arr[i]) {
            		// 기준보다 작으면 물이 고일 수 있으므로 값을 더해준다
				sum += a - arr[i];
			} else {
            		// 기준보다 크면 물이 고일 수 없으므로 기준을 갱신
				a = arr[i];
			}
		}
		for (int i = W - 1; i > posi; i--) {
			if (b > arr[i]) {
				sum += b - arr[i];
			} else {
				b = arr[i];
			}
		}
		System.out.println(sum);
	}
}
この方式は132 msに達するより速い.
コテ通まではまだ遠いですね~~元気を出して、ピナコ