글 읽기 - 여기서 더 고쳐야 할 반례가 있나요?

treestackque 1년 전 0

min과 MAX의 차이가 1일 경우 무한 루프에 빠지는 경우를 대비해서 break조건문은 추가했습니다

10 80

2 2 3 5 9 12 12 16 18 19 집어넣었을 때 답도 1로 나옵니다

이제 시간초과는 안 뜨지만 답이 틀렸다고 뜨네요

못 찾은 반례가 또 있는 걸까요?

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

int cut(vector<int>&t, int H) {
	
	int tmp=0;

	for (auto p = t.begin(); p != t.end(); p++) {
		if (*p > H)tmp +=  * p - H;
	}

	return tmp;
}

int main() {

	int N; int M;
	cin >> N >> M;

	vector<int>trees; trees.push_back(0);

	for (int i = 0; i < N; i++) {
		int t;
		cin >> t;
		trees.push_back(t);
	}

	sort(trees.begin(), trees.end());

	int min = trees[0]; int MAX = trees[N];

	int H = (min + MAX) / 2;

	while (cut(trees, H) != M) {
		if (cut(trees, H) > M) { min = H;   H = (min + MAX) / 2; if (MAX - min ==1) { H = min; break; } }
		else { MAX = H;   H = (min + MAX) / 2; if (MAX - min ==1) { H = min; break; } }
	}

	cout << H;

	return 0;
}

yhj1937 1년 전 1

tmp 값이 int 범위를 넘어갈 수 있습니다.

treestackque 1년 전 1

해결했습니다 감사합니다

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

문제

문제

출처

ICPC

여기서 더 고쳐야 할 반례가 있나요?

treestackque 1년 전 0

yhj1937 1년 전 1

treestackque 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말