글 읽기 - 반례 찾기 좀 부탁드리겠습니다.

dyddkdlel33 5년 전 0

ㅂ반례 찾기좀 부탁드립니다. 그리고 long long을 너무 남발 하는 것 같은데 어디까지만 long long을 사용해야 하나요...

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;

long long arr[1000001]; // 나무의 수는 최대 100만개

long long Sum2(long long arr[], long long H, long long start, long long end, long long target) { // mid보다 작은 값들도 같이 계산해야 함.
	long long total = 0;

	for (int i = end; i >= start; i--) {
		if (target <= total)  // total 값이 더 커지면 더 이상 계산할 필요가 없다.
			break;
		else {
			if (arr[i] - H < 0)
				continue;
			else
				total = total + (arr[i] - H);
		}
	}
	return total;
}

long long Sum1(long long arr[], long long H, long long mid, long long end) {// mid 보다 큰 값들만 계산해주면 됨.
	long long total = 0;

	for (int i = end; i > mid; i--) {
		if (arr[i] - H < 0) 
			continue;
		else
			total = total + (arr[i] - H);
	}
	return total;
}
long long BinarySearch(long long arr[], long long count, long long target) { // target은 원하는 M
	long long total;
	long long H; // H의 최대값을 계산하라.
	long long start = 0;
	long long end = count - 1;
	long long mid = (start+end) / 2;

	H = arr[mid]; // mid 다음부터 값을 계산하면 됨.

	total = Sum1(arr, H, mid, end); // total은 mid보다 큰 값 중 9-H, 10-H, 11-H ...

	if (target == total)
		return H;  // target과 베었을 때 값이 같으면 가장 이상적.
	else if (target < total) { // 너무 많이 베었으면 톱날을 키워서, 베는 것을 줄인다.
		while (target < total) {
			H++;
			total = Sum1(arr, H, mid, end);
		}
		return H; // 조건을 만족하면서 H를 증가시키면서 최대값을 만든다.
	}
	else { // target > total
		while (target > total) {
			H--;
			total = Sum2(arr, H, start, end, target); // target을 넣어준 이유는 target보다 total 값이 커지면 종료시키도록 하기 위함.
		}
		return H;
	}
}
int main() {
	long long N, M; // N은 나무의 수, M은 집으로 가져가려고 하는 나무의 길이
	long long result;

	scanf("%lld %lld", &N, &M);

	for (int i = 0; i < N; i++) {
		scanf("%lld", &arr[i]);
	}
	sort(arr, arr + N);
	
	result = BinarySearch(arr, N, M);
	
	printf("%lld\n", result); // 절단기 높이의 최대값, 높이는 1,000,000,000보다 작거나 같은 양의 정수

	return 0;
}

luniro 5년 전 0

N, M, result, arr[] 모두 int 범위 이내입니다 start, end, mid도 모두 int 범위 이내이긴 한데, 지금처럼 mid를 계산하려면 int일 경우 오류가 발생할 수 있습니다 total만 long long으로 하시면 될 것 같습니다

그리고 함수 이름이 binarySearch이긴 한데, 내용은 1씩 증감시키면서 비교하는 방식이라 시간초과가 발생할 것 같습니다 이진탐색으로 구현하세요

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

문제

문제

출처

ICPC

반례 찾기 좀 부탁드리겠습니다.

dyddkdlel33 5년 전 0

luniro 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말