글 읽기 - 소방차문제 풀이 질문입니다.

mbkim95 6년 전 0

파이프와 소방차의 위치가 오름차순으로 입력받는다는 조건때문에

lowerbound 이용해서 풀면 되겠다고 생각해서 풀었는데 오답이라고 나오네요..

제 생각에는 아무리 생각해봐도 lowerbound로 풀면 정답이 나올 것 같은데

테스트 케이스를 돌려봐도 다 맞는거 같은데 제 생각이 잘못된걸까요ㅠㅠ

lowerbound로 풀면 안된다면 이유가 뭔지 알려주시면 감사하겠습니다ㅠㅠ

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

int n, m;
int f[100000], h[100000];

int solve(int idx, int s, int e){
	int m;

	while(e-s > 0){
		m = (s+e)/2;
		if(f[idx] > h[m])
			s = m+1;
		else
			e = m;
	}
	return min(abs(h[e] - f[idx]), abs(h[e-1] - f[idx]));
}

int main(){
	cin >> n >> m;
	for(int i=0; i<n; i++)
		cin >> h[i];

	for(int i=0; i<m; i++)
		cin >> f[i];

	int ret = 0;
	for(int i=0; i<m; i++)
		ret += solve(i, 0, n-1);
	cout << ret << endl;
}

chogahui05 6년 전 1

lower_bound로 푸셨다고요?

3
50 81
14 15

mbkim95 6년 전 0

답변해주셔서 감사합니다ㅋㅋ

말씀하신 테스트케이스를 입력하면 6이 나와서 이것도 정답인거같은데.. 뭐가 문제일까요ㅠㅠ

djm03178 6년 전 1

"하나의 펌프에는 하나의 소방차만 연결할 수 있다."

mbkim95 6년 전 0

너무 제 풀이에만 몰두해서 문제의 전제조건을 제대로 확인안하고 넘어갔었나보네요ㅠㅠ 답변달아주셔서 정말 감사합니다!!

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

문제

문제

출처

ICPC

소방차문제 풀이 질문입니다.

mbkim95 6년 전 0

chogahui05 6년 전 1

mbkim95 6년 전 0

djm03178 6년 전 1

mbkim95 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말