글 읽기 - [C++] 틀렸다고 나오는데 코드 어느 부분이 문제 있지 잘모르겠습니다..

brain404 1년 전 0

주어진 예제에 대한 결과와 질문에서 올라온 반례도 결과가 잘 나왔는데 틀리다고 나옵니다... 어떤 부분이 틀린 것인지 몰라서 질문드립니다..

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll lw_bound(ll n, ll M, ll max, ll arr[]) {
	ll L = 1;
	ll R = max;
	ll mid;
	ll total = 0;

	while(L < R) {
		mid = (L + R) / 2; 
		total = 0;
		for(int i = 0; i < n; i++) {
			if(arr[i] > mid) {
				total += arr[i] - mid;
			}
		}
		if(total > M) L = mid + 1;
		else R = mid;

	}
	return R;
}


int main() {
	ll N = 0;
	ll M = 0;
	ll arr[1000001] = {};
	ll max = 0;

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

	for(int i = 0; i < N; i++) {
		scanf("%lld", &arr[i]);
		if(max < arr[i]) max = arr[i];
	}

	printf("%lld\n", lw_bound(N, M, max, arr));
}

dldyddlwl 1년 전 1

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll lw_bound(ll n, ll M, ll max, ll arr[]) {
	ll L = 1;
	ll R = max;
	ll mid;
	ll total = 0;

	while(L <= R) {    // L과 R이 같을 때에도 해봐야합니다. 그 값이 조건에 해당한다는 보장이 없기 때문입니다.
		mid = (L + R) / 2; 
		total = 0;
		for(int i = 0; i < n; i++) {
			if(arr[i] > mid) {
				total += arr[i] - mid;
			}
		}
		if(total >= M) L = mid + 1; // 저희가 구하고자 하는것은, 최댓값이므로, 가능한 오른쪽으로 밀어야합니다
                                    // 민다는게 조금 표현이 그런데, 둘중에 오른쪽 칸을 선택해야한다는 겁니다.
		else R = mid-1;        // mid-1이 아니라 mid로 하면, 계속 반복되어서 시간초과가 발생할 수도 있습니다!

	}
	return R;
}

brain404 1년 전 0

감사합니다!!

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

문제

문제

출처

ICPC

[C++] 틀렸다고 나오는데 코드 어느 부분이 문제 있지 잘모르겠습니다..

brain404 1년 전 0

dldyddlwl 1년 전 1

brain404 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말