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

alohajihwan 7년 전 0

세 용액 문제를 N^2*logN 만에 푼거 같은데 시간 초과가 납니다..

어떻게 해결 해야 할까요??ㅠㅠ

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
#include<queue>
#include<functional>
using namespace std;

#define INF 20000000000
#define ll long long int
int n;
ll a[5001];
ll Abs(ll t)
{
	if(t < 0) return -t;
	else return t;
}
int binary(int p, int q, int i, int j)
{
	if(p==q) return p;
	int mid = (p+q)/2;
	if(Abs(a[mid]+a[i]+a[j]) < Abs(a[mid+1]+a[i]+a[j]))
		binary(p,mid,i,j);
	else
		binary(mid+1,q,i,j);	
}
int main()
{
	cin >> n;
	int p = 0;
	int m = 0;
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		if(a[i] > 0) p++;
		else m++;
	}
	sort(a+1,a+1+n);
	if(p == n || m == n){
		if(a[1] < 0){
			printf("%lld %lld %lld\n",a[n-2],a[n-1],a[n]);
			return 0;
		}
		else{
			printf("%lld %lld %lld\n",a[1],a[2],a[3]);
			return 0;
		}
	}
	ll minV = INF;
	ll x,y,z;
	for(int i=1;i<=m;i++){
		int j,k;
		for(j=i+1;j<n;j++){
			k = binary(j+1,n,i,j);
			if(minV > Abs(a[i]+a[j]+a[k])){
				minV = Abs(a[i]+a[j]+a[k]);
				x = a[i];
				y = a[j];
				z = a[k];
			}
		}
		
	}
	cout << x << " " << y << " " << z << endl;
}
			
		

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

문제

문제

출처

ICPC

세 용액 문제 질문입니다.

alohajihwan 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말