[문제해결 기법 1주차] 과소비 알람

 

 

https://mygumi.tistory.com/72

이진 탐색 알고리즘 Binary Search :: 마이구미

 

: 계수정렬과 바이너리 정렬(중앙값 찾기)를 이용한 것이다. 계수정렬을 하니까 좀더 시간이 주는듯?

: 바이너리 소트 잘 모르니까 무조건 다시 정렬하는 법 해보기~!!!!

#include <iostream>
using namespace std;

int main() {
	int testcase;
	cin >> testcase;
	while (testcase--) {
		int a, b;
		int arr[201];
		int brr[200001];
		int alarm = 0;
		for (int i = 0; i <= 200; i++) {
			arr[i] = 0;
		}
		cin >> a >> b; 
		for (int j = 0; j < a; j++) {
			cin >> brr[j];
		}
		for (int i = 0; i < b; i++) {
			arr[brr[i]]++;
		}

		for (int j = 0; j < a - b; j++) {
			int count = 0;
			int x = -1;
			int y = -1;
			int med = b / 2;
			for (int i = 0; i < 201; i++) {
				count += arr[i];
				if (x == -1 && count > med) {
					x = i;
				} 
				if (y == -1 && count > med - 1) {
					y = i;
				}
			}
			double m = 0;
			if (b % 2 == 1) {
				m = x;
			}
			else {
				m = double(x + y) / 2;
			}

			if (m * 2 <= brr[j + b]) {
				alarm++;
			}

			arr[brr[j]]--;
			arr[brr[j + b]]++;
		}
		cout << alarm << '\n';
	}

}