글 읽기 - 도와주세요!!!!!

pos10022 6년 전 0

이진 탐색으로 했는데 왜 시간 초과가 나오나요?

#include <stdio.h>
#include <algorithm>

using namespace std;

int n,m;
int a[500005],b[500005];

int count(int s)
{
	int cnt=0;

	for(int i=s;i<=n;i++) {
		if(a[i]!=a[s]) break;
		else cnt++;
	}
	for(int i=s-1;i>=1;i--) {
		if(a[i]!=a[s]) break;
		else cnt++;
	}
	return cnt;
}

int bs(int s,int e,int x)
{
	if(s>e) return 0;
	int mid=(s+e)/2;
	if(a[mid]==x) return count(mid);
	else if(a[mid]>x) return bs(s,mid-1,x);
	else return bs(mid+1,e,x);
}

int main()
{
	int i,j;

	scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%d",&a[i]);
	scanf("%d",&m);
	for(i=1;i<=m;i++) scanf("%d",&b[i]);
	sort(a+1,a+1+n);
	for(i=1;i<=m;i++) printf("%d ",bs(1,n,b[i]));
	printf("\n");
}

jseo 6년 전 1

모든 원소가 같을때에 위 알고리즘의 시간 복잡도가 어떻게 될까요.

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

문제

문제

출처

ICPC

도와주세요!!!!!

pos10022 6년 전 0

jseo 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말