一. 题目-田忌赛马
给定两个只包含数字的数组a, b, 调整数组a里面数字的顺序,使得尽可能多的a[i] > b[i]。数组a和b中的数字各不相同。
输出所有可以达到最优结果的a数组数量
输入描述:
输入的第一行是数组a中的数字,其中只包含数字,每两个数字之间相隔一个空格,a数组大小不超过10
输入的第一行是数组b中的数字,其中只包含数字,每两个数字之间相隔一个空格,b数组大小不超过10
输出描述:
输出所有可以达到最优结果的a数组数量
补充说明:
示例1
输入:
11 8 20
10 13 7
输出:
1
说明:
最优结果只有一个,a = [11, 20, 8],故输出1
示例2
输入:
11 12 20
10 13 7
输出:
2
说明:
有两个a数组的排列可以达到最优结果,[12, 20, 11]和[11, 20, 12],故输出2
示例3
输入:
1 2 3
4 5 6
输出:
6
说明:
a无论如何都会全输,故a任意排列都行,输出所有a数组的排列,6种排法
二.解题思路
问题的关键在于调整数组a的顺序,使得尽可能多的a[i] > b[i]。为了达到最优结果,我们可以采用贪心的策略。具体思路如下&