글 읽기 - 시간 초과 오류..

bongster 8년 전 0

제가 binary search를 이용해서 풀었는데, 시간초과가 나와서요.

혹시 제가 놓치고 있는 부분이 있을까요?

예제 케이스의 경우 대해서 돌려봤을때는 제대로 나와서요.

#include <iostream>

using namespace std;

long long a[100001];

bool check(long long time, int &n, long long &m) {
	// 해당 시간 대에 처리할수 있는 사람의 수가 m 보다 작은지 비교
	int count=0;
	for (int i=1; i<= n; i++) {
		count = count + (time / a[i]);
	}
	return count < m;
}
int main() {
	int n;
	long long m;
	scanf("%d %lld", &n, &m);
	
	long long mx_time=0;
	long long mn_time=1000000000;
	for (int i=1; i<=n; i++) {
		scanf("%lld", &a[i]);
		mx_time = max(mx_time, a[i]);
		mn_time = min(mn_time, a[i]);
	}
	long long l = (mn_time * m) / n, r = (mx_time * m) / n;
	long long ans = r;
	while (l <= r) {
		long long mid = (l + r) / 2;
		if (check(mid, n, m)) {
			l = mid + 1;
		} else {
			r = mid - 1;
			ans = min(ans, mid);
		}
	}
	printf("%lld\n", ans);
	return 0;
}

booboo 8년 전 0

라인 9의 int count=0; 이게 문제네요...

bongster 8년 전 1

booboo 님 감사합니다.

int type이라 문제 였네요.

이걸 long long으로 바꾸니 통과하였습니다. 감사합니다.

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

문제

문제

출처

ICPC

시간 초과 오류..

bongster 8년 전 0

booboo 8년 전 0

bongster 8년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말