package y2019.Algorithm.array;

/**

 * @ProjectName: cutter-point

 * @Package: y2019.Algorithm.array

 * @ClassName: ArrayPairSum

 * @Author: xiaof

 * @Description: 561. Array Partition I

 * Given an array of 2n integers, your task is to group these integers into n pairs of integer,

 * say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

 *

 * Input: [1,4,3,2]

 *

 * Output: 4

 * Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).

 *

 * 给定一个长度为2n(偶数)的数组，分成n个小组，返回每组中较小值的和sum，使sum尽量大

 * @Date: 2019/7/2 17:24

 * @Version: 1.0

 */

public class ArrayPairSum {

    public int solution(int[] nums) {

        //这个题的求每组中小的值，最后求和，尽量大，那就是说相近的数据最好放一组，不然差距很大，会导致最后值相差很大

        quikSort(nums, 0, nums.length);

        //排完序之后，叉开获取数据和即可

        int result = 0;

        for(int i = 0; i < nums.length; i += 2) {

            result += nums[i];

        }

        return result;

    }

    private void quikSort(int[] array, int left, int right) {

        if(left < right) {

            int mid = partitionSort(array, left, right);

            quikSort(array, left, mid);

            quikSort(array, mid + 1, right);

        }

    }

    private int partitionSort(int[] array, int left, int right) {

//        if(left == right || left > right) {

//            return left;

//        }

        int midValue = array[left];

        int start = left;

        int end = right;

        //分区排序

        do {

            do { ++ start; } while(start < right && array[start] < midValue);

            do {

                --end;

            } while(left < end && array[end] > midValue);

            //交换

            if(start < end) {

                int temp = array[start];

                array[start] = array[end];

                array[end] = temp;

            }

        } while(start < end);

        //交换完毕之后，最后吧坑填上,这个时候left和right错开一位，所以right再left的左边

        array[left] = array[end];

        array[end] = midValue;

        return end;

    }

    public static void main(String args[]) {

        int A1[] = {1,4,3,2};

        ArrayPairSum fuc = new ArrayPairSum();

        System.out.println(fuc.solution(A1));

    }

}