글 읽기 - multimap 이용 해서 풀었는데 시간초과 나네요 ㅠㅠ

sanha93 4년 전 0

multimap 에 셋트로 저장하고

맨처음부터 카드가 클때까지 돌리면서

바로 뒤집어주거나, 뒤집는 수가 작아서 두번 계산할 여지가 있으면

큐에 넣었다가 빼주는 걸로 했는데..

혹시 이렇게 하는게 아니라

카드 뒤집는걸 멀티셋으로 바꾸고 몇번 뒤집히는지를 확인 하는게 더 나은걸까요?

#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;

	return 0;
}

sanha93 4년 전 0

아.. 아니면 마스크 만들어서 처리하는게 더 빠르려나요..?

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

multimap 이용 해서 풀었는데 시간초과 나네요 ㅠㅠ

sanha93 4년 전 0

sanha93 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말