개똥벌레

#include <iostream> #include <vector> #include <algorithm> #define MAXN 200001 #define MAXH 500001 using namespace std; int suk[MAXH], jong[MAXH], res[MAXH]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); //각 구간별로 장애물 개수를 센다. int n, h; cin >> n >> h; int cnts = 0, cntj = 0; for (int i = 0; i < n; i++) { //맨 처음에는 석순부터 시작하고 그 이후에는 종유석과 석순이 번갈아가며 나타난다. int tmp; cin >> tmp; if (i % 2 == 0) { //석순 suk[cnts++] = tmp; } else { jong[cntj++] = tmp; } } sort(suk, suk + cnts ); sort(jong, jong + cntj ); for (int i = 1; i <= h; i++) { //현재 구간에서 석순은 이 높이 이상인경우, 종유석은 이 높이까지 내려온 경우에 장애물 개수 ++ int idx = lower_bound(suk, suk + cnts, i) - suk; res[i] += cnts - idx; int idx2 = lower_bound(jong, jong + cntj, h - i + 1) - jong; res[i] += cntj - idx2; } sort(res+1, res + h+1); int minCnt = 1; for (int i = 2; i <= h; i++) { if (res[i] <= res[1]) { minCnt++; } } cout << res[1] << " " << minCnt << '\n'; return 0; }