题目描述

小美有一个长度为 $n$ 的数组 $a$ ，下标从 $1$ 开始，这个数组满足 $a_i<a_{i+1}, (1\leq i<n)$。

思路：贪心

因为我们要使得差值的数不同的尽可能多，那么就是去考虑差值 1, 2, 3, ... 为多少。

那么 $a_1$ 必然为 $1$ ，$a_2=a_1+1$, $a_3=a_2+2, ... a_i = a_{i-1}+i$ ，直到 $a_i=a_{i-1}+i>m$ 停止。此外，你还要保证后续的每个差值都至少为 $1$ 。

所以 $a_i=a_{i-1}+i$ 需要保证：

• $a_i\leq m$
• $a_{j+1}>a_j(j\geq i)$ 且 $a_{j+1}\leq m$