글 읽기 - c++ set.lower

sontaewjd 1년 전 0

29번째 줄에서
s.lower_bound(num)이 아닌

auto wh = lower_bound(s.begin(), s.end(), num, greater<int>());
로 하면 시간초과가 나네요... 둘이 차이점이 있나요??

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <tuple>
#include <set>
using namespace std;
int G, P;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> G >> P;
	set<int, greater<int>> s;
	for (int i = 1; i <= G; i++)
		s.insert(i);
	int res = 0;
	int g;
	bool end = false;
	for (int i = 0; i < P; i++)
	{
		cin >> g;
		if (end)
			continue;
		bool f = false;
		auto wh = s.lower_bound(g);
		if (wh != s.end())
		{
			s.erase(wh);
			f = true;
			res++;
		}
		if (!f)
			end = true;
	}
	cout << res;
	return 0;
}

djm03178 1년 전 0

그냥 lower_bound는 set에 대해 선형 시간이 걸립니다.

sontaewjd 1년 전 0

특이하네요... 감사합니다!!

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

문제

문제

출처

ICPC

c++ set.lower_bound() 질문

sontaewjd 1년 전 0

djm03178 1년 전 0

sontaewjd 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말