글 읽기 - 2073 세용액 질문입니다.

leejoo2038 5년 전 0

용액들을 오름차순으로 정렬하고 나서 가장 작은값과 가장 큰값을 가지고 가운데 값들중 이분탐색으로 합이 0에 가장 가까운 값을 찾습니다.

그리고 나서 앞을 하나 줄이고 나서 가운데중에서 이분 탐색으로 하나 찾고 뒤를 하나 줄이고 가운데중에서 이분 탐색으로 하나 찾아가면서 세 수의 합이 가장 작은것을 저장해가는 것입니다. 위의 알고리즘이 틀렸나요??

#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<math.h>
#include<limits.h>
int f(int, int, long long, long long *);
int main() {
	int i, j, k, l, r, x, y;
	long long sum1, p, q, u, B[3];
	scanf("%d", &k);
	long long* A = (long long*)malloc(k * sizeof(long long));
	for (i = 0; i < k; i++) scanf("%lld", &A[i]);
	if (k == 3) {
		std::sort(A, A + 3);
		for (i = 0; i < 3; i++) printf("%lld ", A[i]);
		return 0;
	}
	std::sort(A, A + k);
	sum1 = A[0] + A[k - 1];
	p = A[1], j = 1;
	for (i = 2; i < k - 1; i++) {
		if (llabs((sum1 + A[i])) < llabs((sum1 + p))) {
			p = A[i]; j = i;
		}
		else break;
	}
	B[0] = A[0], B[1] = A[k - 1], B[2] = A[j];
	u = A[0] + A[k - 1] + A[j];
	for (l = 0, r = k - 1; l + 2 < r;) {
		x = f(l + 1, r - 2, A[l] + A[r - 1], A);
		p = A[l] + A[r - 1] + A[x];
		y = f(l + 2, r - 1, A[l + 1] + A[r], A);
		q = A[l + 1] + A[r] + A[y];
		if (llabs(p) < llabs(q)) {
			r--;
			if (llabs(p) < llabs(u)) {
				B[0] = A[l], B[1] = A[r], B[2] = A[x];
				u = p;
			}
		}
		else {
			l++;
			if (llabs(q) < llabs(u)) {
				B[0] = A[l], B[1] = A[r], B[2] = A[y];
				u = q;
			}
		}
	}
	std::sort(B, B + 3);
	printf("%lld %lld %lld", B[0], B[1], B[2]);
	return 0;
}
int f(int left, int right, long long sum, long long *A) {
	int a = left, b = right, c;
	long long s1;
	do {
		c = (a + b) / 2;
		s1 = sum + A[c];
		if (left <= c && llabs((sum + A[(a + c - 1) / 2])) < llabs(s1)) b = c - 1;
		else if (c <= right && llabs((sum + A[(c + b + 1) / 2])) < llabs(s1)) a = c + 1;
		else break;
	} while (a <= b);
	return c;
}

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

문제

문제

출처

ICPC

2073 세용액 질문입니다.

leejoo2038 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말