90 lines
1.4 KiB
Markdown
90 lines
1.4 KiB
Markdown
|
# 排队问题
|
|||
|
|
|
|||
|
|
n名战士站成一排。每个战士都有唯一的评分；
|
|||
|
|
|
|||
|
|
每3个战士可以组成一个作战单位，分组规则如下：
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
从队伍中选出下标分别为i、j、k的3名战士，他们的评分分别为Si, Sj, Sk；
|
|||
|
|
|
|||
|
|
队伍需要满足：Si<Sj<Sk 或者 Si>Sj>Sk，其中：0<=i<j<k<n;
|
|||
|
|
|
|||
|
|
给定一组数据，按上述规则可以组建的作战单位数量及对应的值；
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
例如：
|
|||
|
|
|
|||
|
|
输入：1 = [2, 5, 3, 4, 1]
|
|||
|
|
|
|||
|
|
输出：3
|
|||
|
|
|
|||
|
|
说明：队伍序号，(2, 3, 4)、(5, 4, 1)、(5, 3, 1)；
|
|||
|
|
|
|||
|
|
输入：1 = [2, 1, 3]
|
|||
|
|
|
|||
|
|
输出：0
|
|||
|
|
|
|||
|
|
解释：不符合条件。
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
问题：
|
|||
|
|
|
|||
|
|
我们要找什么？
|
|||
|
|
|
|||
|
|
如何去找？
|
|||
|
|
|
|||
|
|
关键点1：从前到后所有的组合（3个元素）
|
|||
|
|
|
|||
|
|
所有组合如下：
|
|||
|
|
|
|||
|
|
[2, 5, 3]
|
|||
|
|
|
|||
|
|
[2, 5, 4]
|
|||
|
|
|
|||
|
|
[2, 5, 1]
|
|||
|
|
|
|||
|
|
[2, 3, 4]
|
|||
|
|
|
|||
|
|
[2, 3, 1]
|
|||
|
|
|
|||
|
|
[2, 4, 1]
|
|||
|
|
|
|||
|
|
[5, 3, 4]
|
|||
|
|
|
|||
|
|
[5, 3, 1]
|
|||
|
|
|
|||
|
|
······
|
|||
|
|
|
|||
|
|
[3, 4, 1]
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
关键点2：找到符合规则的组合
|
|||
|
|
|
|||
|
|
条件1：v1>v2>v3
|
|||
|
|
|
|||
|
|
条件2：v1<v2<v3
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
实现思路：
|
|||
|
|
|
|||
|
|
1. 三层遍历：
|
|||
|
|
|
|||
|
|
第一层：i_1,...,i_n
|
|||
|
|
|
|||
|
|
第二层：i_2,...,i_n
|
|||
|
|
|
|||
|
|
第三层：i_3,...,i_n
|
|||
|
|
|
|||
|
|
组合形式：(i_1, i_2, i_3), (i_1, i_2, i_4), ..., (i_1, i_2, i_n)
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
以2开头组合，如下图：
|
|||
|
|
|
|||
|
|
|