글 읽기 - 7469번 세그먼트 트리는 다했는데 이진탐색으로 찾는 방법을 모르겠습니다..

gkfkagkfka12 6년 전 0

고수분들...제발 살려주십쇼 6시간을 넘게 한 문제만 붙들고 있네요...

질문들도 다 보고 구글링도 계속했는데 세그먼트 트리로 풀려면 제 풀이는 다음과 같습니다.

1. 배열을 정렬기준으로 세그먼트 트리를 만든다.

2. 임의의 X를 기준으로 X보다 작은 숫자의 개수가 K보다 작거나 같음/더 큼 기준으로 이진탐색을 하면 마지막 X가 답이 된다.

근데 여기서 2번을 어떻게 구현해야 하는지 모르겠습니다. 임의의 X를 어떤 것으로 잡아야 할지랑 이진탐색을 세그먼트 트리 위에서부터 재귀적으로 아래로 내려오면서 하는지를 잘 모르겠습니다. 도움주시면 감사하겠습니다.

코드는 2번이 구현되지 않은 상태입니다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>

// 합병정렬 알고리즘을 이용해서 세그먼트 트리의 부분벡터 정렬
std::vector<int> Merge(std::vector<int> a, std::vector<int> b)
{
	std::vector<int> temp;
	int i = 0, j = 0, a_size = a.size(), b_size = b.size();

	while (i < a_size && j < b_size) {
		if (a[i] < b[j]) {
			temp.push_back(a[i]);
			i++;
		}
		else {
			temp.push_back(b[j]);
			j++;
		}
	}

	if (i == a_size) {
		while (j < b_size) {
			temp.push_back(b[j]);
			j++;
		}
	}
	else if (j == b_size) {
		while (i < a_size) {
			temp.push_back(a[i]);
			i++;
		}
	}

	return temp;
}


std::vector<int> init(int arr[], std::vector<int> tree[], int node, int start, int end)
{
	if (start == end) {
		tree[node].push_back(arr[start]);
		return tree[node];
	}

	int mid = (start + end) / 2;
	return tree[node] = Merge(init(arr, tree, node * 2, start, mid), init(arr, tree, node * 2 + 1, mid + 1, end));
}

int main(void)
{
	int n, m; std::cin >> n >> m;
	int *arr = new int[n];
	for (int i = 0; i < n; i++) scanf("%d", &arr[i]);

	int h = static_cast<int>(std::ceil(std::log2(n)) + 1);
	int tree_size = static_cast<int>(std::pow(2.0, h) - 1);

	// 세그먼트 트리 생성
	std::vector<int> *tree = new std::vector<int>[tree_size + 1];

	// 초기화
	init(arr, tree, 1, 0, n - 1);


	//int i, j, k;
	//while (m--) {
		//scanf("%d %d %d", &i, &j, &k);
		//i--; j--;
		//printf("%d\n", ParametricSearch(tree, arr, 0, n - 1, i, j, k));
	//}

	delete[] arr, tree;
	return 0;
}

atomzeno 6년 전 0

예제를 가지고 보면

1 5 2 6 3 7 4 를 쪼개서

대충 생각난 거론

1층: 1 2 3 4 5 6 7

2층: 1 2 5 3/ 4 6 7

3층: 1 5/2 3/ 6/4 7

4층: 1/5/2/6/3/7/4

이렇게 쪼개시고 하시면 됩니다.... 2 5 3을 예로 들면

(2,5)=(2,2)+(3,4)+(5,5)이니 임의의 수 i에 대해

1.각 부분에서 i이하의 수의 개수 세기(각 구간은 정렬되 있으므로 이진탐색)

2. i가 각 부분에 나오는지(이진탐색하면서 알 수 있음)

를 log(n)2만에 알 수 있으므로, O(Q*log(n)2+n*log(n))만에 해결될 것으로? 보입니당

gkfkagkfka12 6년 전 0

그 임의의 수 i를 어떤기준으로 잡아야 되죠?

atomzeno 6년 전 0

1~N사이에서 이진탐색하는 거로?

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

문제

문제

출처

ICPC

7469번 세그먼트 트리는 다했는데 이진탐색으로 찾는 방법을 모르겠습니다..

gkfkagkfka12 6년 전 0

atomzeno 6년 전 0

gkfkagkfka12 6년 전 0

atomzeno 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말