[伯俊]#2473歳溶液

質問する

KOI建設科学研究所は多様な酸性溶液とアルカリ性溶液を持っている.各溶液には整数があり、その溶液の特性を表す.酸性溶液の特性値は、1〜10000000の正の整数で表され、塩基性溶液の特性値は−1〜10000000の負の整数で表される.
3種類の溶液を等量混合した溶液の特性値は、混合に用いる各溶液の特性値の和として定義される.同研究所は等量の3種類の溶液を混合し,特性値が最もゼロに近い溶液を作製した.
例えば、与えられた溶液の特性値が[2,6,−97,−6,98]であり、特性値が−97であり、特性値が−98の溶液と混合されると、特性値が−1である溶液を作製することができ、この溶液は特性値が0に最も近い溶液である.参考として、特性値が0に近い混合溶液を3種類のアルカリ溶液のみまたは3種類の酸性溶液のみで作製する場合もある.
酸性溶液とアルカリ性溶液が与えられた場合、等量の3つの異なる溶液を混合し、特性値が0に近い3つの溶液を探し出すプログラムを作成する.

入力

1行目は、溶液全体の数Nを入力する.Nは3以上5000以下の整数である.2行目には、溶液特性値を表すN個の整数が与えられ、その間にスペースが隔てられている.これらの数字はいずれも-10000000以上10000000以下です.N個の溶液の特性値が異なり、酸性溶液またはアルカリ性溶液のみが入力される場合もある.

しゅつりょく

1行目の出力特性値は0に近い3種類の溶液の特性値である.出力が必要な3種類の溶液は特性値の昇順に出力される.プロパティ値が0の場合、2つ以上の場合、いずれかを出力します.

入力例1

5
-2 6 -97 -6 98

サンプル出力1

-97 -2 98

入力例2

7
-2 -3 -24 -6 98 100 61

サンプル出力2

-6 -3 -2

に答える

この問題は二重ポインタで解くことができる.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long[] arr = new long[N];
        long[] ans = new long[3];
        long min = Long.MAX_VALUE;

        String[] input = br.readLine().split(" ");

        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(input[i]);
        }

        Arrays.sort(arr);

        for(int i=0; i<N-2; i++) {
            int left = i+1;
            int right = N-1;

            while(left<right) {
                long sum = arr[left]+arr[right]+arr[i];

                if(min>Math.abs(sum)) {
                    min = Math.abs(sum);
                    ans[0] = arr[i];
                    ans[1] = arr[left];
                    ans[2] = arr[right];
                }

                if(sum<0)
                    left++;
                else
                    right--;
            }
        }

        System.out.println(ans[0]+" "+ans[1]+" "+ans[2]);
    }
}