69 正数数组的最小不可组成和-进阶问题
Table of Contents

ac

import java.util.Arrays;
import java.util.Scanner;


public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static void main(String[] args){
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            int num = sc.nextInt();
            arr[i] = num;
        }
        Arrays.sort(arr);
        System.out.println(getAns(arr, n));
    }

    static long getAns(int[] sortedArr, int n){
        // [1, range] 能够被 arr[0...i-1] 算出来
        // arr[i];
        // arr[i] > range + 1; 则不会出现sum为 range + 1 了,因为最小就是 arr[i] > range + 1
        // arr[i] <= range + 1; [1, range + arr[i]]
        long range = 0;
        for(int i=0;i<n;i++){
            if(sortedArr[i] > range + 1){
                return range + 1;
            }else {
                range = range + sortedArr[i];
            }
        }
        return range + 1;
    }
}
/*
3
1 4 2

8

3
1 2 5

4
 */