글 읽기 - 반례를 못찾겠네요

sdy1437 3년 전 0

이분탐색 부분을

while(lo<=hi)

if()hi=mid-1;

else lo=mid+1;

이렇게 바꾸면 통과되네요

하지만 두 코드의 차이를 모르겠습니다.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n, c, ans;
vector<int> vec;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n >> c;
	vec.resize(n, 0);
	for (int i = 0; i < n; i++) cin >> vec[i];
	sort(vec.begin(), vec.end());
	int lo = 1, hi = vec[n - 1] - vec[0];
	
	while (lo + 1 < hi) {
		int mid = (lo + hi) / 2;
		int start = vec[0];
		int cnt = 1;
		for (int i = 1; i < n; i++) {
			if (vec[i] - start >= mid) {
				start = vec[i], cnt++;
			}
		}
		if (cnt < c)hi = mid;
		else ans = mid,lo = mid;
	}
	cout << ans << '\n';
	return 0;
}

BothEarRim 1년 전 0

간단한 반례 드립니다.

이걸로 분석해보세요.

INPUT
2 2
0 1

ANSWER
1

틀린 코드의 출력
0

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

문제

문제

출처

ICPC

반례를 못찾겠네요

sdy1437 3년 전 0

BothEarRim 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말