글 읽기 - 시간초과만.. 10번째..

ddojung 6년 전 0

무엇을 바꿔야 될까요?ㅠㅠ접근을 아예잘못하고있는건지 모르겠습니다.............ㅠㅠㅠㅠ

#include <stdio.h>
#define MAX 1000000
long long tree[MAX];
int main() {
	long long N, M;
	scanf("%lld %lld", &N, &M);
	for (int i = 0; i < N; i++) {
		scanf("%lld", &tree[i]);
	}
	long long max=0;
	long long i;
	for (i = 0; i < N; i++) {
		if (max < tree[i]) {
			max = tree[i];
		}
	}

	while (max>0) {
		long long cnt = 0, result=0;
		for (i = 0; i < N; i++) {
			if (tree[i] > max) {
				result = result + (tree[i] - max);
				cnt++;
			}
		}
		if ((M + cnt > result && M < result) || M == result) {
			printf("%lld", max);
			return 0;
		}
		else if (result < M) {
			max = max - (max / 2);
		}
		else if (result > M) {
			max = max + (max / 2);
		}
	}
}

chogahui05 6년 전 1

이분탐색 비스무리하게는 해 놓으셨는데.. 범위가 잘못 변하고 있어요.

그렇기 때문에 아래 TC에서 시간초과가 납니다.

보통 이분 탐색을 할 때는 left, right, mid 이렇게 3개의 값을 가지고 mid라는 것을 왔다리 갔다리 하거든요.

max값이 어떻게 변하는지는 확인해 보셨나요??

/*
4 1
20 15 10 17
*/

ddojung 6년 전 0

오 무엇이문제였는지 해결됐습니다! 감사합니다~!ㅎㅎ

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

문제

문제

출처

ICPC

시간초과만.. 10번째..

ddojung 6년 전 0

chogahui05 6년 전 1

ddojung 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말