글 읽기 - upper_bound 와 자료형에 관해 질문

seokjw96 3년 전 0

자료형에 관해서는 s+e를 하는 과정에서 오버플로우가 발생할 수 있다는 걸 알았습니다. 그런데 문제를 풀때 가장 큰 최대의 길이를 구하는 것이므로 upperbound 를 구하고 아래 소스코드처럼 e-1 을 해주면 왜 답이 아닐까요??

#include <iostream>
#include <algorithm>
#define MAX 10001
using namespace std;

int arr[MAX];
int k, n;


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> k >> n;
	long long e;
	for (int i = 0; i < k; i++) {
		cin >> arr[i];
		e = max(e, arr[i]);
	}
	long long s = 1;
	int ans = 0;
	while (s < e) {
		long long cnt = 0;
		long long mid = (s + e) / 2;
		for (int i = 0; i < k; i++) {
			int h = arr[i];
			cnt += h / mid;
		}
		if (cnt >= n) {
			s = mid + 1;
		}
		else {
			e = mid;
		}
	}
	cout << e - 1;
	return 0;
}

seico75 3년 전 0

일단 e가 초기화가 안되어서 문제가 발생할 수 있을 것 같습니다.

일반적으로는 29라인이 통과가 되면 mid는 가능하므로 mid를 포함하는 범위로 s, e를 조정하고

else 일 경우 mid를 포함하지 않도록 더 작은 범위로 s, e를 조정해야할 것 같습니다.

그런데,

질문에서 정확한 값을 찾는 것이 아니라 upperbound를 찾고 1을 빼면 되지 않냐는 것 같은데...

5 5

1 1 1 1 1

를 하면 안되지 않을까요?

seokjw96 3년 전 0

아 그렇네요 감사합니다

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

문제

문제

출처

ICPC

upper_bound 와 자료형에 관해 질문

seokjw96 3년 전 0

seico75 3년 전 0

seokjw96 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말