1000ms

Difficulty: 5

所属公司 : 蚂蚁

时间 :2025年9月21日

算法与标签>贪心算法

会员或题库专享

请先，开通会员或购买题库蚂蚁机考题库，可解锁完整内容。

购买蚂蚁机考题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（蚂蚁机考题库），可解锁完整内容。

购买题库开通会员

解题思路

核心贪心：能切就立刻切

从左到右维护当前未结束段的 $\gcd$ 与长度。当第一次出现

\gcd \le \text{当前长度}

题目内容

给定一个长度为 $n$ 的正整数数组 { $a_1,a_2,…,a_n$ } ;

我们称一段连续子数组 $a_l,a_{l+1},...,a_r$ 为优美段，当且仅当这段子数组的 $gcd(a_l,a_{l+1},...,a_r)≤r-l+1$ ;

请将整个数组划分成 $k$ 段互不相交的优美段，覆盖原数组每个位置，求使 $k$ 最大化，输出最大值 $k$ 。