글 읽기 - 반례를 못찾겠습니다.

31n5ang 3년 전 0

61%에서 틀렸는데 반례를 찾지 못하고 있습니다.

의미가 없다는 걸 알겠지만 혹시나 저와 비슷한 분이 계실까 해서 적었습니다.

0 ~ n - 1 중
1 ~ n - 2를 차례대로 가운데 인덱스로 정한 후, 투 포인터로 0에 가까운 값을 갱신했습니다.

#include <bits/stdc++.h>

using namespace std;
 
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define endl "\n"
#define ll long long 

const int N = 5005;

int n, r1, r2, r3;
int a[N];

void solve(int m_i) {
    ll cur = a[r1] + a[r2] + a[r3];
    int l = 0, r = n - 1;
    while (l < m_i && m_i < r) {
        ll sum = a[l] + a[r] + a[m_i];
        if (abs(sum) < abs(cur)) {
            r1 = l;
            r2 = m_i;
            r3 = r;
        }
        if (sum < 0) {
            l++;
        } else if (sum > 0) {
            r--;
        } else {
            break;
        }
    }
}

int main() {
    IOS;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a + n);
    r1 = 0, r2 = 1, r3 = n - 1;
    for (int i = 1; i < n - 1; i++) {
        solve(i);
    }
    cout << a[r1] << " " << a[r2] << " " << a[r3];
    return 0;
}

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

문제

문제

출처

ICPC

반례를 못찾겠습니다.

31n5ang 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말