package com.jiucaiyuan.net.algrithm.audition;



import java.util.ArrayList;

import java.util.Comparator;

import java.util.List;

import java.util.PriorityQueue;



public class MrTianHorseRacing {

    /**

     * <pre>

     * 田忌赛马

     * 两个数组没有重复元素，第一个数组固定按照从小道大出场比赛，数组较大的获胜

     * 给出第二个数组可以获得胜利的一个排列

     * 不存在获胜可能返回空数组

     *

     * 2 4 6

     * 1 3 5

     *

     * 按照默认顺序是0:3失败

     * 调整为3 5 1 之后是2:1获胜

     * </pre>

     *

     * @param arr1 团队1，顺序递增

     * @param arr2 团队2，顺序不定

     * @return 返回团队2可以胜利的其中一种排列次序

     */

    public static int[] win(int[] arr1, int[] arr2) {

        if (arr1 == null || arr2 == null || arr1.length != arr2.length) {

            return null;

        }

        //大顶堆

        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {

            public int compare(Integer i1, Integer i2) {

                return i2 - i1;

            }

        });

        for (int e : arr2) {

            queue.add(e);

        }



        List<Integer> result = new ArrayList<>();

        process(arr1, queue, result, arr1.length - 1);



        if (result.size() > arr1.length / 2) {

            int[] res = new int[arr1.length];

            int i = 0;

            for (Integer e : result) {

                res[i++] = e;

            }

            while (!queue.isEmpty()) {

                res[i++] = queue.poll();

            }

            return res;

        }



        return null;

    }



    public static void process(int[] arr, PriorityQueue<Integer> queue, List<Integer> result, int index) {

        if (queue.isEmpty() || result.size() > arr.length / 2) {

            return;

        }

        int e = queue.poll();

        for (int i = index; i >= 0; i--) {

            if (e > arr[i]) {

                result.add(e);

                process(arr, queue, result, i - 1);

                return;

            }

        }

    }



    public static void main(String[] args) {

        // Scanner input=new Scanner(System.in);

        // String str=input.next();

        int[] arr1 = {1, 2, 5, 6};

        int[] arr2 = {4, 3, 5, 1};

        print(win(arr1, arr2));

        int[] arr11 = {1, 4, 3, 5};

        int[] arr22 = {1, 2, 5, 6};

        print(win(arr11, arr22));

    }



    private static void print(int[] win) {

        if (win == null) {

            System.out.println("null");

            return;

        }

        for (int i : win) {

            System.out.print(i + " ");

        }

        System.out.println();

    }

}