백준 14465번 소가 길을 건너간 이유 5 문제풀이(C++)

백준 14465번 소가 길을 건너간 이유 5

아이디어

i ~ i+b 사이의 신호등의 개수를 세면 된다
펜윅트리를 이용하여 해당 위치의 신호등을 업데이트 하고
i ~ i+b 사이의 신호등의 최소개수를 가져온다

문제풀이

#include<bits/stdc++.h>
using namespace std;
#define MAX 100010
#define INF 2'100'000'000
int n, b, k;
int cnt[MAX];
void query(int idx) {
	while (idx <= n + 1) {
		cnt[idx] += 1;
		idx += (idx & -idx);
	}
}
int sum(int idx) {
	int _sum = 0;
	while (idx) {
		_sum += cnt[idx];
		idx -= (idx & -idx);
	}
	return _sum;
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> b >> k;
	for (int i = 0; i < k; i++) {
		int num; cin >> num;
		query(num);
	}
	int _min = INF, left = 1, right = b;
	while (right <= n) {
		_min = min(_min, (sum(right) - sum(left - 1)));
		right += 1, left += 1;
	}
	cout << _min << '\n';
	return 0;
}