글 읽기 - 어떤게 문제일까요

ahrrudals 1년 전 0

테스트 샘플은 통과했는데, 실패로 떠서 뭐가 문제인지 모르겠습니다...

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


int find_pos(long long int pos[], long long int start, long long int end,long long int n,long long int c) {
	long long int left = pos[start];
	long long int right = pos[end];
	long long int ans = -1;
	while (left<=right) {
		long long int mid = (left + right)/2;
		int i = 0;
		int cnt = 1;
		
		for (int j = 0;j < n; j++) {
			if (pos[j] - pos[i] >= mid) {
				cnt = cnt + 1;
				i = j;
			}
		}

		if (cnt >= c) {
			if (ans < mid) ans = mid;
			
			left = mid + 1;
		}
		else right = mid - 1;
	}
	return ans;
}

int main() {
	long long int n, c;
	cin >> n >> c;
	long long int* pos = new long long int[n];
	for (int i = 0;i < n;i++) {
		cin >> pos[i];
	}

	sort(pos,pos+n);
	cout<<find_pos(pos, 0, n - 1, n, c);
}

zenith82114 1년 전 0

ans < mid일 때 ans를 갱신한다는 조건이 잘못된 듯합니다.

ahrrudals 1년 전 1

long long int left = pos[start];를

long long int left =0;로 고치니 해결되었습니다!

zenith82114 1년 전 1

아 그건 발견을 못했는데 그걸 고쳐야 맞는군요.

알려주셔서 고맙습니다. :)

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

문제

문제

출처

ICPC

어떤게 문제일까요

ahrrudals 1년 전 0

zenith82114 1년 전 0

ahrrudals 1년 전 1

zenith82114 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말