[SWEA] 8825 홀수 중간값 피라미드2

출처: SWEA

 Input 

2

4

1 6 3 7 4 5 2

2

3 1 2

 

 Output 

#1 4

#2 2

 

 

---

#include<iostream>
#include<cstdio>
using namespace std;
int n, arr[200000];
 
bool cmp(int x, int mid) {
    return x >= mid;
}
 
bool judgeUpDown(int mid) {
    for (register int i = 1; i <= n - 1; ++i) {
        if (cmp(arr[n - i + 1], mid) == cmp(arr[n - i], mid)) return cmp(arr[n - i], mid);
        if (cmp(arr[n + i - 1], mid) == cmp(arr[n + i], mid)) return cmp(arr[n + i], mid);
    }
    return cmp(arr[1], mid);
}
 
int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);
 
    int testCase; cin >> testCase;
    for (int tc = 1; tc <= testCase; ++tc) {
        cin >> n;
        for (int i = 1; i <= 2 * n - 1; ++i)
            cin >> arr[i];
 
        int left = 1, right = 2 * n - 1, answer = 1;
        while (left <= right){
            int mid = (left + right) >> 1;
            if (judgeUpDown(mid)) {
                answer = mid;
                left = mid + 1;
            }
            else right = mid - 1;
        }
 
        // 정답 출력
        printf("#%d %d\n", tc, answer);
    }
}