코드
#include <map>
#include <queue>
#include <iostream>
#include <stdio.h>
using namespace std;
int main() {
int m, n;
int geta, getb, middle;
long long int result = 0;
multimap<int, int> cards;
queue<pair<int, int>> save;
scanf(" %d %d", &m, &n);
for (int i = 0; i < m; i++) {
scanf(" %d %d ", &geta, &getb);
cards.insert(make_pair(geta, getb));
}
for (int i = 0; i < n; i++) {
scanf(" %d", &middle);
auto iter = cards.begin();
while (iter->first <= middle) {
if (iter->second <= middle) {
save.push(make_pair(iter->first, iter->second));
}
else {
cards.insert(make_pair(iter->second, iter->first));
}
iter++;
cards.erase(cards.begin());
if (iter == cards.end())
break;
}
while (!save.empty()) {
cards.insert(make_pair(save.front().second, save.front().first));
save.pop();
}
}
for (auto iter = cards.begin(); iter != cards.end(); iter++) {
result += iter->first;
}
cout << result;
cin >> result;
return 0;
}
주저리
도대체 어떻게 짜야 하는 걸까…
자료의 스왑 시간과, 탐색 시간을 줄이기 위해서
멀티맵을 사용하였다.
이거보다 직접 뒤집는걸 시뮬레이션 했을떄 더 빠른 방법은 생각이 나질 않는다..
오늘 안에 도저히 풀어 올리는게 불가능하다고 생각이 되어
내일 이나 언제든 다시 도전 해보려고 한다..
지금 제일 최적으로 떠오르는 대안은
앞면카드[]
뒷면카드[]
앞뒤포인터[]
이런식으로 하나하나 다 대조하는거 뿐…
맵도 시간초과가 났는데 이게 가능 할지는 모르겠다.
특이한 케이스 ( 예를 들자면 매번 마다 다 뒤집히는 바람에 큐에 넣고 빼는일이 많아지는경우)
를 제외하면 도저히 시간 초과 날 이유는 없어보인다.
6월11일 오늘도 실패해서 과거 업로드 했던걸 끌어서 올렸다..
마치 웹툰 작가가 세이브 원고를 묵혀두고 처리하느는낌?
우선 priority_queue 를 사용해서 해보는게 가장 좋을 거 같다.