글 읽기 - 자꾸 오답이 뜨네요. 반례가 있나요?

altjd46 6년 전 0

자꾸 오답이 뜨네요. 반례가 있나요?

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;
int n[1000000];
int main(){
	int N, M;	
	int low = 0, mid, high, temp = 0;
	int r = 0;
	long long result = 0;
	scanf("%d %d", &N, &M);
	int i = 0;
	while (i < N){
		scanf("%d", &n[i++]);
	}
	sort(n, n + N);
	int min = 0, max = 0, min_n=0;
	high = N-1;
	while (low <= high){
		mid = (low + high) / 2;
		
		int j = mid + 1;
		result = 0;
		while (result < M&&j<N){		
			temp = n[j] - n[mid];
			result = result + temp;
			j++;
		}
		if (result == M&&j==N){
			r= n[mid];	
			break;
		}
		else if (result < M){
			high = mid - 1;
			max = n[mid] - 1;
		}
		else{
			low = mid + 1;
			min = n[mid]+1;
			min_n = mid + 1;
			
		}
	} 
	if (r == 0){
		while (min <= max){
			mid = (max + min) / 2;
			result = 0; temp = 0;
			int j = min_n;
			while (result < M&&j < N){
				temp = n[j] - mid;
				result = result + temp;
				j++;
			}
			r = mid;
			if (result == M&&j==N){
				break;
			}
			else if (result < M){
				max = mid - 1;
			}
			else{
				min = mid + 1;

			}
		}
	}
	printf("%d\n", r);
	return 0;
}

ghkdtkden93 6년 전 1

high = N - 1이아니라 n[N-1]이죠. 이유는 생각해보세요

모르면 또 질문올리세요

altjd46 6년 전 1

감사합니다 ^^

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

문제

문제

출처

ICPC

자꾸 오답이 뜨네요. 반례가 있나요?

altjd46 6년 전 0

ghkdtkden93 6년 전 1

altjd46 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말