[dovelet][분할정복] balanced lineup / b_lineup

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 모두 통과하고 추가로 게시하자.