글 읽기 - 2805 나무자르기 질문이요

eldldl07 5년 전 0

안녕하세요 초보입니다. 다음과 같이 코드를 만들었습니다.

게시판을 보니 다른 분들은 시간 초과가 뜨는데 저는 일단 4 7 20 15 10 17 의 테스트 케이스부터 오류가 뜹니다.

그런데 2 3 2 2, 4 12 13 23 21 32 와 같은 테스트케이스는 문제없이 값이 나옵니다.

4 7 20 15 10 17 의 값이 왜 제대로 나오지 않는건가요?

#include<stdio.h>
#include<algorithm>
using namespace std;
long long s[1000001];
int arr[100001];
int k = 1;

int main(void)
{
	int n, m;
	scanf("%d %d", &n, &m);//n:나무 m:필요한길이
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &s[i]);
	}
	sort(s + 1, s + n + 1);//정렬
	int st = 1;
	int e = s[n];
	int flag = 0;
	while (st <= e)
	{
		long long sum = 0;
		long long mid = (st + e) / 2;
		for (int i = 1; i <= n; i++)
		{
			if (s[i] - mid > 0) {//양수일때만 +
				sum += (s[i] - mid);
			}
		}
		if (sum == m)
		{
			printf("%d", sum);
			flag = 1;
			break;
		}
		else if (sum > m) {
			st = mid + 1;
			arr[k] = mid;
			k++;
		}
		else if (sum < m) {
			e = mid - 1;
		}
	}
	//printf("%d\n", k);
	if (flag == 0)
	{
		sort(arr + 1, arr + 1 + k);
		printf("%d", arr[k]);
	}
	return 0;
}

k5nen 5년 전 1

32행을 봅시다. 출력을 원하는 값은 높이 H입니다. sum은 아닌 것 같네요.

eldldl07 5년 전 0

@rkn04 감사합니다

eldldl07 5년 전 0

flag==0 일때만 고치고 앞에 고치는것을 잊고 있었네요

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

문제

문제

출처

ICPC

2805 나무자르기 질문이요

eldldl07 5년 전 0

k5nen 5년 전 1

eldldl07 5년 전 0

eldldl07 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말