题目内容

小塔拿到了一个数组，他每次操作可以选择任意一个元素$x$使其变成$\sqrt{x}$(向下取整)。

小塔想知道，使得该数组变成非降序，需要至少操作多少次?

贪心

很容易发现后面的数组尽量不要动，所以从后考虑贪心，对于每一个i，贪心到小于$a[i+1]$即可$\\$整体复杂度$o(n)$

代码如下

cpp

#include <bits/stdc++.h>
using namespace std;