글 읽기 - 이분탐색으로 풀었습니다. 그런데..어디부분이 틀렸는지못찼겠습니다 도와주세요 ㅜ

isvara 4년 전 0

이분탐색으로 풀었는데 어디 부분에서 오류가 나는지 모르겠습니다..

#include<stdio.h>
#define Max(a,b) (a > b ? a : b)
long long tree[1000001];
int main() {
	int N;
	long long M, lo = 0LL, ro = 0LL, mid, sum;
	scanf("%d %lld", &N, &M);
	for (int i = 0; i < N; i++) {
		scanf("%lld", &tree[i]);
		ro = Max(tree[i], ro);
	}
	while (lo <= ro) {
		mid = (lo + ro)/2;
		sum = 0LL;
		for (int i = 0; i < N; i++) {
			if (tree[i] > mid) {
				sum += (tree[i] - mid);
			}
		}
		if (sum > M) 
			lo = mid + 1;
		else if(sum<M)
			ro = mid - 1;
		else if(sum==M)
			break;
	}
	printf("%lld\n", mid);
}

surung9898 4년 전 1

반례는 다음과 같습니다.

/*
6 1
0 2 0 0 0 2

answer: 1
output: 2

isvara 4년 전 1

아.. 같다고해서 해를 바로 찾은게 아니고 더 최적의 해가 있을 수 있기 때문에 같더라도 계속 탐색해야하는군요

감사합나다.

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

문제

문제

출처

ICPC

이분탐색으로 풀었습니다. 그런데..어디부분이 틀렸는지못찼겠습니다 도와주세요 ㅜ

isvara 4년 전 0

surung9898 4년 전 1

isvara 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말