프양연 그래도 수명이 / 이진탐색, 구현

1. 이진탐색 2. 구현 레벨을 넣어서 3. 원하는 것에 해당하는지 4. 그 레벨을 mid 로 두고5 5. 최소값을 찾는 것임 6. 이진탐색을 이럴 때 사용하는군

#include <stdio.h> //#define MAX 200001 #define MAX 11 int N, K; int arr[MAX]; int data[MAX]; int max; int min; static void dump() { int i; printf("block={"); for (i = 0; i < N; i++) { printf("%d, ", arr[i]); } printf("}\n"); printf("data={"); for (i = 0; i < K; i++) { printf("%d, ", data[i]); } printf("}\n"); } int ok(int level) { int idxblk = 0; int idx = 0; int cnt = 0; while (idx < N) { if (arr[idx++] <= level) { cnt++; if (cnt == data[idxblk]) { if (idxblk >= K - 1) { return 1; } else { idxblk++; cnt = 0; } } } else cnt = 0; } return 0; } int main(void) { freopen("input.txt", "r", stdin); int test_case, T; long ret = 0; scanf("%d", &T); for (test_case = 1; test_case <= T; test_case++) { scanf("%d %d", &N, &K); max = 0; min = 2147483647; for (int i = 0; i < N; i++) { arr[i] = 0; scanf("%d", &arr[i]); if (arr[i] > max) { max = arr[i]; } if (arr[i] < min) { min = arr[i]; } } for (int i = 0; i < K; i++) { scanf("%d", &data[i]); } int low = min, hi = max; int mid = 0; int result = 0; int answer = 2147483647; while (low <= hi) { mid = (hi + low) / 2; if (ok(mid)) { hi = mid - 1; if (answer > mid) answer = mid; } else { low = mid + 1; } } printf("#%d %d\n", test_case, answer); } return 0; }