글 읽기 - c++ / right값 정하기

pppp1923 3년 전 0

초기 left, right 값을 정답이 될 수 있는 최대, 최소로 지정해 주었습니다.

근데 이 문제의 경우 right 값이 (검사해야하는 사람 수 * 검사대 시간의 최대) 인 것은 구했는데

실제 제한 사항을 따져보면 (10의9승 * 10억)이라 long long이 넘치게 되는데

테스트케이스에 이런 상황은 없다고 가정이 된 것인가요??

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool isPossible(vector<long long>& a, long long x, long long m) {
	int size = a.size();
	long long cnt = 0;
	for (int i = 0; i < size; i++) {
		cnt += x / a[i];
	}
	if (cnt >= m) return true;
	else return false;
}

int main() {
	int n, m; cin >> n >> m;
	vector<long long> a(n);
	long long min = 1000000001;
	long long max = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		if (min > a[i]) min = a[i];
		if (max < a[i]) max = a[i];
	}
	sort(a.begin(), a.end());

	long long left = min;
	long long right = m * max;
	long long ans = 0;
	while (left <= right) {
		long long mid = (left + right) / 2;
		if (isPossible(a, mid, m)) {
			ans = mid;
			right = mid - 1;
		}
		else {
			left = mid + 1;
		}
	}
	
	cout << ans << "\n";
	return 0;
}

djm03178 3년 전 1

10억의 제곱은 long long 범위 안입니다.

구현 방법에 따라 long long을 넘어서 문제가 될 수 있는 케이스도 포함되어 있습니다.

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

문제

문제

출처

ICPC

c++ / right값 정하기

pppp1923 3년 전 0

djm03178 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말