글 읽기 - 반례를 찾지 못 하겠습니다.

adfsfsf 5년 전 0

코드를 아래와 같이 썼습니다.

#include <stdio.h>
#include <stdlib.h>
long long int n, m, *num, count;
int com(const void *a, const void *b);
long long int check(long long int left, long long int right);
int main(void)
{
	long long int i;
	scanf("%lld %lld", &n, &m);
	num = (long long int *)calloc(n, sizeof(long long int));
	for (i = 0; i < n; i++)
		scanf("%lld", &num[i]);
	qsort(num, n, sizeof(long long int), com);
	for (i = 0; i < n - 1; i++)
	{
		if (num[i] == num[i + 1])
			count++;
	}
	if (n == m && count == n - 1)
		printf("%lld\n", check(1, num[n - 1]) + 1);
	else
		printf("%lld\n", check(1, num[n - 1]));
	return 0;
}
int com(const void *a, const void *b)
{
	long long int m = *(long long int *)a, n = *(long long int *)b;
	if (m > n)
		return 1;
	if (m < n)
		return -1;
	return 0;
}
long long int check(long long int left, long long int right)//이분탐색 함수
{
	long long int mid = (left + right) / 2, i, j, hsum = 0;
	for (i = 0; i < n; i++)
		hsum += num[i] / mid;//hsum에 생성되는 랜선 수 저장
	if (hsum >= m)
	{
		if (left > right)
			return mid;
		j = check(mid + 1, right);
		return (mid > j) ? mid : j;
	}
	else
	{
		if (left > right)
			return 0;
		return check(left, mid - 1);
	}
}

djm03178 5년 전 2

1 1

adfsfsf 5년 전 0

그렇네요. 감사합니다.

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

문제

문제

출처

ICPC

반례를 찾지 못 하겠습니다.

adfsfsf 5년 전 0

djm03178 5년 전 2

adfsfsf 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말