피너클의 it공부방
백준 7469 K번째 수 (c++) : 피너클 본문
728x90
반응형
https://www.acmicpc.net/problem/7469
머지소트 트리를 만들고 이분 탐색을 이용해서 풀었다.
int n, m;
int arr[100001];
vector<int> segtree[4 * 100001];
입력받을 배열과 머지소트 트리를 위한 segtree를 만들어준다.
void init(int node, int start, int end, int left, int right) {
if (end < left || right < start) return;
if (start == end) {
segtree[node].push_back(arr[start]);
return;
}
int mid = (start + end) / 2;
init(node * 2, start, mid, left, right);
init(node * 2 + 1, mid + 1, end, left, right);
int left_length = segtree[node * 2].size();
int right_length = segtree[node * 2 + 1].size();
int left_now = 0, right_now = 0;
while (left_now < left_length && right_now < right_length) {
if (segtree[node * 2][left_now] < segtree[node * 2 + 1][right_now]) {
segtree[node].push_back(segtree[node * 2][left_now]);
left_now++;
}
else {
segtree[node].push_back(segtree[node * 2 + 1][right_now]);
right_now++;
}
}
while (left_now < left_length) {
segtree[node].push_back(segtree[node * 2][left_now]);
left_now++;
}
while (right_now < right_length) {
segtree[node].push_back(segtree[node * 2 + 1][right_now]);
right_now++;
}
}
머지소트트리 init함수이다. 자신의 자식 트리에서 받아온 것들을 크기에 맞춰서 자기 자신에게 넣어주면 된다.
int main(int argc, char** argv)
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> arr[i];
init(1, 1, n, 1, n);
입력을 받고 init해준다.
while (m-- > 0) {
int i, j, k;
cin >> i >> j >> k;
int left = -100000000, right = 100000000;
그 후 이분탐색을 할것이다. left와 right는 1e9로 해준다. 주어지는 숫자의 최대 범위이다.
while (left <= right) {
int mid = (left + right) / 2;
int v = query(1, 1, n, i, j, mid);
if (v < k) left = mid + 1;
else if(v >= k) right = mid - 1;
}
cout << left << '\n';
}
그 후 이분탐색을 돌리며 숫자를 맞춰가면 된다.
query는 i와 j 사이의 값들 중 mid보다 작거나 같은 값의 수를 보낸다.
i와 j사이의 값들중 mid보다 작은 값 v가 우리가 찾고자 하는 k보다 작다면 left를 높여주고
아니면 right를 내린다.
그후 left를 출력하면 된다.
int query(int node, int start, int end, int left, int right, int val) {
if (end < left || right < start) return 0;
if (left <= start && end <= right) {
auto it = upper_bound(segtree[node].begin(), segtree[node].end(), val);
return it - segtree[node].begin();
}
int mid = (start + end) / 2;
return query(node * 2, start, mid, left, right, val) + query(node * 2 + 1, mid + 1, end, left, right, val);
}
query함수다.
upper_bound를 이용해서 수를 찾아준다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, m;
int arr[100001];
vector<int> segtree[4 * 100001];
void init(int node, int start, int end, int left, int right) {
if (end < left || right < start) return;
if (start == end) {
segtree[node].push_back(arr[start]);
return;
}
int mid = (start + end) / 2;
init(node * 2, start, mid, left, right);
init(node * 2 + 1, mid + 1, end, left, right);
int left_length = segtree[node * 2].size();
int right_length = segtree[node * 2 + 1].size();
int left_now = 0, right_now = 0;
while (left_now < left_length && right_now < right_length) {
if (segtree[node * 2][left_now] < segtree[node * 2 + 1][right_now]) {
segtree[node].push_back(segtree[node * 2][left_now]);
left_now++;
}
else {
segtree[node].push_back(segtree[node * 2 + 1][right_now]);
right_now++;
}
}
while (left_now < left_length) {
segtree[node].push_back(segtree[node * 2][left_now]);
left_now++;
}
while (right_now < right_length) {
segtree[node].push_back(segtree[node * 2 + 1][right_now]);
right_now++;
}
}
int query(int node, int start, int end, int left, int right, int val) {
if (end < left || right < start) return 0;
if (left <= start && end <= right) {
auto it = upper_bound(segtree[node].begin(), segtree[node].end(), val);
return it - segtree[node].begin();
}
int mid = (start + end) / 2;
return query(node * 2, start, mid, left, right, val) + query(node * 2 + 1, mid + 1, end, left, right, val);
}
int main(int argc, char** argv)
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> arr[i];
init(1, 1, n, 1, n);
while (m-- > 0) {
int i, j, k;
cin >> i >> j >> k;
int left = -100000000, right = 100000000;
while (left <= right) {
int mid = (left + right) / 2;
int v = query(1, 1, n, i, j, mid);
if (v < k) left = mid + 1;
else if(v >= k) right = mid - 1;
}
cout << left << '\n';
}
return 0;
}
전체코드다.
728x90
반응형
'백준' 카테고리의 다른 글
백준 1214 쿨한 물건 구매 (c++) : 피너클 (2) | 2025.08.22 |
---|---|
백준 11585 속타는 저녁 메뉴 (c++) : 피너클 (0) | 2025.08.21 |
백준 4013 ATM (c++) : 피너클 (0) | 2025.08.19 |
백준 18186 라면사기 (Large) (c++) : 피너클 (2) | 2025.08.18 |
백준 18185 라면 사기 (Small) (c++) : 피너클 (1) | 2025.08.17 |
Comments