프로그래밍/문제

BOJ - 최솟값 ( 세그먼트트리)

lee ho jun 2020. 9. 24. 14:15
반응형

www.acmicpc.net/problem/10868

 

10868번: 최솟값

N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는

www.acmicpc.net

세그먼트 트리 개념을 잡을 수 있는 기초적인 문제이다.

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
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <stdio.h>
#include <vector>
#include <cmath>
#define INF 1410065407
using namespace std;
 
int *tree;
int *arr;
 
 
 
int init(int start , int end , int node)
{
    if(start == end)
        return tree[node] = arr[start];
    
    
    int mid = (start + end)/2;
    
    return tree[node] = min(init(start , mid , node*2) , init(mid+1 , end , node*2 +1));
    
}
 
int find2(int start , int end , int node , int l , int r)
{
    if(l >end || r < start)
        return INF;
    
    if(start <= l && r <=end)
        return tree[node];
    
    int mid = (l + r) /2;
    
    return min(find2(start ,end , node*2 , l , mid) ,find2(start, end , node*2+1 , mid+1 , r));
    
}
 
int main(void)
{
    int N , M;
    
    scanf("%d %d" , &N , &M);
    
    arr= new int[N];
    tree = new int[N*4];
    
    
    for(int i = 0 ; i < N ; i++)
        scanf("%d",&arr[i]);
 
 
//    cout<<N<<" "<<M<<endl;
    
    int temp;
    temp = init(0 , N-1 , 1);
    
    
    int s , e;
    
    for(int i = 0 ; i < M ; i++)
    {
        scanf("%d %d" , &s , &e);
        temp = find2(s-1 , e-1 , 1 , 0 , N-1);
        printf("%d\n",temp);
    }
    
    return 0;
}
 
cs

 

 

반응형