글 읽기 - 이 문제 upper_bound 사용하면 안되나요??

jumpingz 7년 전 0

문제를 어떻게 해결해야할지는 알겠는데.. 처음에는 lower_bound 사용하다가 1 2 1 1 1 같은 데이터에서는 답이 안나오는걸 확인해서 upper_bound로 변환햇는데도 여전히 틀리네요...

위 두 함수들이 어떤역할을 하는지 공부하고 했는데.. 좀 부족해서 그런지 왜 틀렷는지를 모르겠습니다..

#include <cstdio>
#include <algorithm>
#include <math.h>
#pragma warning(disable:4996)
using namespace std;

int A[500000], B[500000];

int main()
{
	int i, N, index, max = 0;

	scanf("%d", &N);

	for (i = 0; i < N; i++)
	{
		scanf("%d", &A[i]);
		B[i] = A[i];
	}

	sort(B, B + N);

	for (i = 0; i < N; i++)
	{
		index = upper_bound(B, B + N, A[i]) - B;

		if (i > index)
		{
			if (i - index > max)
				max = i - index;
		}
	}

	printf("%d", max + 2);
	return 0;
}

circle 7년 전 0

순서가 그대로 들어갔을 때 (ex : 1 2 3 4 5) 고려하시면 될거 같습니다.

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

문제

문제

출처

ICPC

이 문제 upper_bound 사용하면 안되나요??

jumpingz 7년 전 0

circle 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말