반응형
https://www.acmicpc.net/problem/3020
3020번: 개똥벌레
개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이
www.acmicpc.net
1. 석순 진행 과정
01234
2. 종유석 진행 과정
01234
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
#include <iostream>
#include <algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int n, h, down[100001], up[100001], min_cnt = 1e9, seg_cnt;
int find(int *arr, int x) {
int s = 0;
int e = n/2;
int ans = n/2;
while (s <= e) {
int mid = (s + e) / 2;
if (x <= arr[mid]) {
e = mid - 1;
ans = mid;
}
else
s = mid + 1;
}
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> h;
rep(i, n / 2)
cin >> down[i] >> up[i];
sort(down, down + n / 2);
sort(up, up + n / 2);
for (int i = 1; i <= h; i++) {
int down_cnt = n / 2 - find(down, i);
int up_cnt = n / 2 - find(up, h + 1 - i);
int cnt = down_cnt + up_cnt;
if (cnt < min_cnt) {
min_cnt = cnt;
seg_cnt = 1;
}
else if (cnt == min_cnt)
seg_cnt++;
}
cout << min_cnt << ' ' << seg_cnt;
}
|
cs |
반응형