글 읽기 - 시간 초과

dohyeokkim 8년 전 0

이거 erase랑 insert 때문에 n^2 되어서 터지는 거죠?? (나머지는 nlogn이고...?)

그리고 이 문제와는 별개로 1초에 연산을 어느 정도 할 수 있다고 생각하면 되나요?

#include <cstdio>
#include <algorithm>
#include <vector>
#include <climits>
#include <cstdlib>

using namespace std;

vector<int> dat;

int b_search(int x, int st, int ed){
  if (st + 1 == ed)
    return dat[st];

  int mid = (st + ed) / 2;
  
  if (dat[mid] == x)
    return x;
  else if (x < dat[mid]){
    if (abs(dat[mid - 1] - x) < abs(x - dat[mid]))
      return b_search(x, st, mid);
    else
      return dat[mid];
  }
  else{
    if (abs(dat[mid + 1] - x) < abs(x - dat[mid]))
      return b_search(x, mid, ed);
    else
      return dat[mid];
  }
}

int main(){
  int n, ans_a, ans_b, tmp_a, tmp_b, sum = INT_MAX;

  scanf("%d", &n);
  dat.resize(n);

  for (int i = 0; i < n; i++){
    scanf("%d", &dat[i]);
  }

  sort(dat.begin(), dat.end());

  for (int i = 0; i < n; i++){
    tmp_a = dat[i];
    dat.erase(dat.begin() + i);
    tmp_b = b_search(-1 * tmp_a, 0, n - 1);

    if (abs(tmp_a + tmp_b) < sum){
      ans_a = tmp_a;
      ans_b = tmp_b;
      sum = abs(tmp_a + tmp_b);
    }

    dat.insert(dat.begin() + i, tmp_a);
  }

  printf("%d %d", min(ans_a, ans_b), max(ans_a, ans_b));

  return 0;
}

onjo0127 8년 전 0

보통 1초에 반복문을 1억 번 정도 돌릴 수 있습니다.

반복문 내부에 따라서 더 빨라질 수도, 느려질 수도 있습니다.

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

문제

문제

출처

ICPC

시간 초과

dohyeokkim 8년 전 0

onjo0127 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말