반응형
문제 출처 :
https://www.acmicpc.net/problem/10868
알고리즘 분석 :
문제 해결에 필요한 사항
1. 세그먼트 트리 :: http://www.crocus.co.kr/648
세그먼트 트리 가장 기본 문제이다.
update과정이 필요없이 초기 과정으로 최솟값을 형성하고
쿼리 과정으로 최솟값을 구하면 된다.
소스 코드 :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | #include <iostream> #include <cstdio> #include <cmath> #include <vector> #include <algorithm> #define INF 1500000000 using namespace std; int init(vector<int> &arr, vector<int> &tree, int node, int start, int end) { if (start == end) return tree[node] = arr[start]; int mid = (start + end) / 2; return tree[node] = min(init(arr, tree, node * 2, start, mid), init(arr, tree, node * 2 + 1, mid + 1, end)); } int query(vector<int> &tree, int node, int start, int end, int left, int right) { if (left > end || right < start) return INF; if (left <= start && end <= right) return tree[node]; int mid = (start + end) / 2; return min(query(tree, node * 2, start, mid, left, right), query(tree, node * 2 + 1, mid + 1, end, left, right)); } int main() { int n, m; scanf("%d %d", &n, &m); int h = (int)ceil(log2(n)); int tree_size = (1 << (1 + h)); vector<int> arr(n); vector<int> tree(tree_size); for (int i = 0; i < n; i++) scanf("%d", &arr[i]); init(arr, tree, 1, 0, n - 1); while (m--) { int left, right; scanf("%d %d", &left, &right); int ans = query(tree, 1, 0, n - 1, left - 1, right - 1); printf("%d\n", ans); } return 0; } // This source code Copyright belongs to Crocus // If you want to see more? click here >> | Crocus |
반응형
'Applied > 알고리즘 문제풀이' 카테고리의 다른 글
[11404번] 플로이드 (2) | 2017.04.12 |
---|---|
[8979번] 올림픽 (0) | 2017.04.12 |
[2414번] 게시판 구멍 막기 (0) | 2017.04.12 |
[1867번] 돌멩이 제거 (0) | 2017.04.12 |
[11779번] 최소비용 구하기 2 (0) | 2017.04.11 |