글 읽기 - 문제 힌트 좀 주시면 안될까요??ㅠㅠ

kce0206 4년 전 0

어떻게 접근해야하는지 모르겠어서...

이분탐색으로 물채우는거까진 만들었는데

물 빼는걸 어떻게 해야하는지 모르겠어요..

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> high;  //벽 높이
vector<int> water;  //물 높이
int t, tidx = 0;
int binarysearch(int s, int e);
int main() {
	//freopen("Text.txt", "r", stdin);  //
	cin >> t;
	while (tidx++ < t) {
		high.clear();
		int n, tmp;
		cin >> n;
		for (int i = 0; i < n; i++) {  //벽 높이 입력
			cin >> tmp;
			high.push_back(tmp);
		}
		water.assign(n - 1, 0);
		int res = binarysearch(0, n - 1);  //물 가득 채우기

		int max_ = 0;
		for (int i = 0; i < water.size(); i++) {  //1번자리 비우고, 2번자리 비우고,3번자리 비우고..
			water.assign(n - 1, 0);        //비웠을 때의 물 양은
			int pumped = binarysearch(0, i);  //비운 칸 왼쪽부분이랑
			water.assign(n - 1, 0);  
			pumped += binarysearch(i + 1, n - 1);  //비운 칸 오른쪽 부분의 합이다.
			if (max_ < abs(res - pumped))  //처음 가득 채웠을 때와 비운 상태의 갭이 최대보다 크면 갱신
				max_ = abs(res - pumped);
		}
		cout << max_<<endl;
	}
	return 0;
}
int binarysearch(int s, int e) {  //이분탐색으로 각 범위에서 통일되야하는 높이를 찾는다
	if (s+1 > e)
		return 0;
	int sum = 0;
	int max_ = -1, maxidx = 0;
	for (int i = s + 1; i <= e; i++) {  //시작점부터 끝점까지 보다가
		if (high[s] <= high[i]) {  //시작보다 큰 벽 만나면 바로 멈추고
			max_ = high[i];
			maxidx = i;
			break;
		}
		if (max_ <= high[i]) {  //큰 벽을 못만나면 그나마 큰 벽을 찾는다
			max_ = high[i];
			maxidx = i;
		}
	}

	if (maxidx == e) {  //찾은 벽이 끝점과 같으면 이 범위는 같은 높이로 다 채워질 수 있다는 뜻이다
		int lower = (high[s] > max_) ? max_ : high[s];  //이때, 시작점과 끝점 중에서 더 낮은 높이로 채운다
		for (int i = s; i < maxidx; i++) {
			water[i] = lower;
			sum += lower;
		}
		return sum;
	}
	sum+=binarysearch(s, maxidx);  //시작점~찾은벽
	sum+=binarysearch(maxidx, e);  //찾은벽~끝점
	return sum;                       //으로 다시 쪼갠다
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

문제 힌트 좀 주시면 안될까요??ㅠㅠ

kce0206 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말