#XXSY26JAT4. 红军的突击行动
红军的突击行动
红军的突击行动
题目描述
在红军长征途中,先遣队发现前方狭长的山谷中,敌军沿路设立了 n 个连成一排的封锁据点。每个据点都有一定的驻军数量,我们用一个包含 n 个正整数的数组 a 来表示,其中 a[i] 代表第 i 个据点的敌军兵力。 为了以最小的代价突破封锁,红军指挥员制定了如下的“突击战术”:
首先,侦察兵会在当前剩余的所有据点中,找出兵力最多的那个据点作为主攻目标。如果兵力最多的据点有多个,为了尽可能向前推进,红军会选择最靠前(即数组中下标最大)的那个。 随后,红军发起突击,拿下该主攻据点,并顺势将它及其之后(下标>=它)的所有据点全部扫清。
请你编写程序计算,红军总共需要发起多少次“突击行动”,才能将所有据点全部拔除(即数组变为空)?
输入格式
第一行包含一个整数 n(数学公式: 1≤n≤),表示初始时敌军据点的总数量。
第二行包含 n 个整数 数学公式: ,依次表示从左到右每个据点的敌军兵力,数字之间用一个空格分隔。
输出格式
输出一行,包含一个整数,表示红军需要发起的突击行动总次数。
输入输出样例
5
2 1 2 3 1
3
5
2 2 2 2 2
5
说明提示
在第一个样例中,数组是 [2,1,2,3,1]。对其执行的操作如下:
首先,选择第 4 个元素。移除最后两个元素,数组变为 [2,1,2];
接着,选择第 3 个元素。移除最后一个元素,数组变为 [2,1];
最后,选择第 1 个元素。移除两个元素,因此在 33 次操作后数组变为空。
在第二个样例中,初始据点兵力为 [2, 2, 2, 2, 2]。
第一次突击:最大兵力为 2,最靠右的是第 5 个据点。拔除它后,剩余 [2, 2, 2, 2]。
后续突击:每次都会选择最靠右的那个据点并只拔除它。总共需要 5 次行动。
数据规模与约定
2≤n≤