글 읽기 - 52%에서 실패가 발생합니다.

dbsdy123 6년 전 0

upper bound형식으로 짜서 N보다 큰 수가 처음등장하는 위치에서 -1한 값을 출력해주는 코드입니다.

#include <cstdio>
using namespace std;

long long lines[10000], max;
int K, N;
int check(int mid){
	int ret = 0;
	for (int i = 0; i < K; ++i) {
		ret += lines[i] / mid;	
	}

	return ret;
}

int main(int argc, char *argv[])
{
	scanf("%d %d", &K, &N);
	for (int i = 0; i < K; ++i) {
		scanf("%lld", lines+i);
		if(max < lines[i]) max = lines[i];
	}

	long long l = 1, r = max;
	while (r - l > 0) {
		long long m = (l + r) / 2;
		if(check(m) >= N)
			l = m + 1;
		else
			r = m;
	}

	printf("%lld\n", r-1);
	return 0;
}

khj94811 6년 전 0

check 함수가 long long이 아니군요!

dbsdy123 6년 전 0

지적 감사합니다. 그런데 역시 또한 52%에서 실패했습니다..

nlkey2022 5년 전 0

반례

1 1

1

답 1 입니다.

rlawldud335 4년 전 0

저 또한 52퍼에서 틀렸다고 나오는데 왜 이런걸까요? 답답하네요

ppsrac 4년 전 0

line 26~line 29처럼 짜면 답이 max값이 될 때 문제가 됩니다.

아마 위 코드의 경우 K값이 반드시 r=max 값일때라는 가정이 들어가있는 것 같습니다.(저 역시 그랬습니다.)

입력값으로

4 1

100

100

2

1

이 주어진다면 답이 100이 되고 위 코드에서 오류가 나게 됩니다.( 코드를 실행하면 99가 답이 되겠죠 )

https://ideone.com/JnWxA1

ppsrac 4년 전 0

윗 댓글을 수정하면 맞는 답이 100이고 실행값이 99가 나옵니다. r=max+1로 두면 좋을것 같습니다.

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