dovelet 20 단계 분할정복
balanced lineup / b_lineup
http://59.23.113.171/30stair/b_lineup/b_lineup.php?pname=b_lineup
1차 풀이
|
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 |
#include <iostream>
using namespace std;
int kee[50100];
int out[200100];
int main(void)
{
int n, q, i, s, e, max, min;
scanf("%d %d", &n, &q);
for(i = 1; i <= n; i++) {
cin >> kee[i];
}
for(i = 1; i <= q; i++) {
cin >> s >> e;
max = 0;
min = 999999;
for(int j = s; j <= e; j++) {
if(max < kee[j]) {
max = kee[j];
}
if(min > kee[j]) {
min = kee[j];
}
}
out[i] = max - min;
}
for(i = 1; i <= q; i++) {
cout << out[i] << endl;
}
return 0;
} |
배열에 저장 후 일일이 비교해서 max와 min 저장 후 차이 계산
test case 10번에서 time limit //
2차 풀이
|
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 |
#include <iostream>
#include <algorithm>
using namespace std;
int kee[50100];
int out[200100];
int main(void)
{
int n, q, i, s, e;
scanf("%d %d", &n, &q);
for(i = 1; i <= n; i++) {
cin >> kee[i];
}
for(i = 1; i <= q; i++) {
cin >> s >> e;
out[i] = *max_element(kee+s, kee+e+1) - *min_element(kee+s, kee+e+1);
}
for(i = 1; i <= q; i++) {
cout << out[i] << endl;
}
return 0;
} |
STL max_element 와 min_element 사용
(max_element와 min_element는 인자로 처음주소와 마지막의 다음 주소를 파라미터로 받는다.
return 값은 해당 값의 주소값을 반환)
test case 8번에서 time limit // 더 느림...
다음 질/답을 참고해보니
index tree에 대해 언급이 있었다.
읽어 본 후 test case 모두 통과하고 추가로 게시하자.
