문제
https://www.acmicpc.net/problem/14464
문제해설
소가 길을 건너는데 닭의 도움이 무조건 필요하다.
닭은 x시간에만 다리를 건너게 해줄 수 있고,
소는 a~b시간 사이에 다리를 건널 수 있다.
a와 b시간 사이에 x가 있어야 소가 다리를 건널 수 있는 것이다.
그렇게해서 최대 몇마리의 소가 다리를 건널 수 있는지 계산하는 문제이다.
닭과 소 둘 다 한번만 이용된다.
문제풀이
처음에는 뭘로 풀어야 하나 생각하다가
소가 건널 수 있는 시간을 선으로 표시해보니 그냥 라인스위핑 문제였다.
소가 건널 수 있는 마지막 시간을 기준으로 우선순위 큐에 넣어주고
닭들을 for문으로 돌면서 가능하다면 카운트를 올려주고 pop해주면 된다.
추가적으로 처리해준 것은 닭도 한번만 쓸 수 있기 때문에
pair로 저장해서 닭을 사용했는지 안했는지 판별해주었다.
전체코드
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
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int, bool>P;
struct cow {
int st, end;
};
bool operator<(cow t, cow u) {
return t.end > u.end;
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n, m; cin >> n >> m;
vector<P>chi;
for (int i = 0; i < n; i++) {
int x; cin >> x;
chi.push_back({ x,false });
}
sort(chi.begin(), chi.end());
priority_queue<cow, vector<cow>>cow;
for (int i = 0; i < m; i++) {
int a, b; cin >> a >> b;
cow.push({ a,b });
}
int res = 0;
while (!cow.empty()) {
for (int i = 0; i < n; i++) {
if (chi[i].first >= cow.top().st && chi[i].first <= cow.top().end && chi[i].second == false) {
res++;
chi[i].second = true;
break;
}
}
cow.pop();
}
cout << res;
return 0;
}