백준 14464번: 소가 길을 건너간 이유 4
소가 길을 건너간 이유 4
아이디어
닭이 도와줄 수 있는 소랑 매칭시켜주면 된다. 그런데 닭이 도와줄 수 있는 소가 2마리 이상이면 어떤 소를 도와줘야 할까?
닭이 도와줄 수 있는 시각을 T라 하고 소 A가 길을 건너는 시간이 [Sa, Ea], 소 B가 길을 건너는 시간이 [Sb, Eb]라 하자. 닭이 소 두 마리를 다 도와줄 수 있는 상황이기 때문에 Sa <= T <= Ea 이고, Sb <= T <= Eb 다. 우리는 E-T가 최대한 작아지는 소를 선택해야 한다. Eb - Ea > 0이면 소 B를 선택했을 때 Eb - Ea 만큼 소를 도와줄 수 있는 기회를 잃기 때문이다.
코드
#include <bits/stdc++.h>
using namespace std;
int C, N, ANS;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
multiset<int> s;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> C >> N;
for (int i = 0; i < C; i++) {
int x;
cin >> x;
s.insert(x);
}
for (int i = 0; i < N; i++) {
int a, b;
cin >> a >> b;
pq.push({b, a});
}
while (!pq.empty()) {
int start = pq.top().second;
int end = pq.top().first;
auto iter = s.lower_bound(start);
if (iter != s.end() && (*iter) <= end) {
ANS++;
s.erase(iter);
}
pq.pop();
}
cout << ANS;
return 0;
}
여담
pair의 앞 원소 기준으로 정렬이 기본값이기 때문에 새로 정의하기 귀찮아서 end를 앞에 넣었다.
그리디 문제 뭔가 확 와닿지가 않아서 연습 많이 해야할듯.
Author And Source
이 문제에 관하여(백준 14464번: 소가 길을 건너간 이유 4), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ks1ksi/백준-14464번-소가-길을-건너간-이유-4저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)