세 용액

Problem link: https://www.acmicpc.net/problem/2473

정렬된 배열에서 서로 다른 3개의 원소 a, b, c를 뽑아 a + b + c = 0이 되도록하는 경우를 헤아리는 문제와 비슷하다.

a <= b <= c가 되도록 순서를 강제해주고, 각 a에 대해서 투 포인터를 진행해준다.

#include <cstdio>
#include <cstdint>
#include <algorithm>
#include <limits>

using namespace std;

inline int64_t ABS(const int64_t x)
{
  return x >= 0 ? x : -x;
}

const int kMaxN = 5000;
const int64_t kMaxAcidity = numeric_limits<int64_t>::max();

int N;
int64_t ACIDITY[kMaxN];

void Solve()
{
  sort(ACIDITY, ACIDITY + N);

  int64_t min_acidity = kMaxAcidity;
  int64_t l1, l2, l3;

  for (int a = 0; a < N; ++a)
  {
    int lo = a + 1;
    int hi = N - 1;

    while (lo < hi)
    {
      int64_t sum = ACIDITY[a] + ACIDITY[lo] + ACIDITY[hi];
      if (ABS(sum) < min_acidity)
      {
        min_acidity = ABS(sum);
        l1 = ACIDITY[a];
        l2 = ACIDITY[lo];
        l3 = ACIDITY[hi];
      }

      if (sum < 0)
      {
        ++lo;
      }
      else
      {
        --hi;
      }
    }
  }

  printf("%ld %ld %ld\n", l1, l2, l3);
}

int main(void)
{
  scanf(" %d", &N);
  for (int it = 0; it < N; ++it)
  {
    scanf(" %ld", &ACIDITY[it]);
  }

  Solve();

  return 0;
}