key points

N個の整数を入力秤

で測定できない整数重量の最大値

Solution

例えば、N=7であるため、7個の重量を入力し、「3 1 6 2 7 30 1」はこれらの数字では計測できない量の中で最大値を求める.
1, 2, 3, 4(1+1+2), 5(2+3), 6, 7, 8(2+6)... これにより、20(1+1+2+3+6+7)に達することができる.したがって、これは21で測定できない浄水重量の中で最も高い値になるだろう.
しかし、もっと洗練された解題方法を見つけた.
入力秤錘重量は[31 6 2 7 301]
昇順で並べ替え、[1,236730]
秤[0]=1で測定できない最大値は2である.
秤[0]=1と秤[1]=1で測定できない最大値は3である.すなわち、最切り上げは、従来の秤錘重量(秤錘[0])では計測できなかった最切り上げ+秤錘[1]の値である.
秤錘[2]=2-->最高値5
秤錘[3]=3->最高価格8
秤錘[4]=6->最高値14
秤錘[5]=7->最高値21
秤錘[6]=30は最高値21より重い.
従って、N個の秤錘で測定できる最大値は21である.
# Code

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        /* Input */
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] array = new int[N];

        for (int i = 0; i < N; i++) {
            array[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(array);

        /* Output */
        int min = 1;
        for (int i = 0; i < N; i++) {
            if (min < array[i]) break;
            min += array[i];
        }

        System.out.println(min);

        br.close();
    }
}

Result

System.out.printlnで作る時間もメモリも少し小さいです.ずっと気になってたけど.bw.書くこととシステム.out.printlnのパフォーマンスの違いを知りたいのですが:)