글 읽기 - 두 코드의 차이를 알고 싶습니다.

adfsfsf 5년 전 0

이 코드는 질문 글에 나온 방법대로 이분탐색을 사용했습니다. 그런데 left == right일 때 답이 mid가 아닌 경우가 있는 것 같습니다. 해당하는 케이스를 알고 싶습니다.

#include <cstdio>
#include <cstdlib>
using namespace std;
int cmp(const void *a, const void *b)
{
	return (*(long long int *)a - *(long long int *)b);
}
int main(void)
{
	long long int n, k, *x, i, j, left, right, mid, min, mmin, t, count;
	scanf("%lld %lld", &n, &k);
	x = new long long int[n];
	for (i = 0; i < n; i++)
		scanf("%lld", &x[i]);
	qsort(x, n, sizeof(long long int), cmp);
	left = 0;
	right = x[n - 1] - x[0];
	mid = (left + right) / 2;
	while (true)
	{
		t = 0;
		count = 0;
		mid = (left + right) / 2;
		for (i = 1; i < n; i++)
		{
			if ((x[i] - x[t]) >= mid)
			{
				t = i;
				count++;
			}
			if (count == (k - 1))
				break;
		}
		if (left == right)
		{
			printf("%lld\n", mid);
			break;
		}
		if (count == (k - 1))
			left = mid + 1;
		else if (count < (k - 1))
			right = mid - 1;		
	}
	return 0;
}

windflower 5년 전 0

반례입니다.

입력:

4 3

1 4 5 9

출력:

adfsfsf 5년 전 0

@windflower

루프 내에서 mid가 한 번이라도 정답을 가리켰고, 그 상태에서 루프가 종료되지 않으면 오류가 나는군요. 덕분에 코드의 문제점을 알았습니다. 감사합니다.

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

문제

문제

출처

ICPC

두 코드의 차이를 알고 싶습니다.

adfsfsf 5년 전 0

windflower 5년 전 0

adfsfsf 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말