[백준-3020] 개똥벌레

해당 높이에 몇개의 장애물이 있는지 누적합을 사용하는 문제이다.

+-prefix 를 사용하여 어디서부터 어디까지 +인지 체크해주면 간단하게 누적합을 구할 수 있으며, O(N)의 복잡도로 문제를 풀 수 있다.

#define _CRT_SECURE_NO_WARNINGS

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <string.h>
#include <math.h>
using namespace std;
typedef long long LL;

int sum[500001];
int main() {
	int n, m, a, b, c;
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a);
		if (i % 2 == 0) {
			sum[m - a + 1] += 1;
		}
		else if (i % 2 != 0) {
			sum[a + 1] -= 1;
			sum[1] += 1;
		}
	}
	vector<int> ans = { 0 };
	for (int i = 1; i <= m; i++) {
		ans.push_back(ans.back() + sum[i]);
	}
	int minn = 200001;
	int mincnt = 0;
	for (int i = 1; i < ans.size(); i++) {
		if (minn > ans[i]) {
			mincnt = 1;
			minn = ans[i];
		}
		else if (minn == ans[i]) {
			mincnt += 1;
		}
	}
	printf("%d %d", minn, mincnt);
	return 0;
}

https://www.acmicpc.net/problem/3020

3020번: 개똥벌레