Milena and Admirer Codeforces Round 910 (Div. 2) B

https://codeforces.com/contest/1898/problem/B

题目大意：有一个长为n的数组，每次操作可以将任意a[i]分成两个数b,c满足b+c=a[i]，然后用这两个数放回原a[i]的位置，问最少多少次操作能使a变成非递减数组

1<=n<=2e5；1<=a[i]<=1e9

思路：因为要让数组变成非递减的，所以对于某个a[i]，如果其>a[i+1],那么就要对其进行操作，无论最后进行几次操作，都应该满足，分出来的这些数是非递减的，最左边的数要>=再左边的一个数，最右边的数要<=再右边的一个数。

????????那么如果我们这样从n到1遍历的话，当前数的分割策略，会影响到左边的数，如果我们令当前数分出来的最左边的数尽可能的大，那么再左边一个数是有可能不用分割的，那么要让分出来的最左边的数最大，就要其他数最小，又要满足非递减，所以应该将这些数平分。

? ? ? ? 我们从n-1遍历到1，如果当前a[i]>a[i+1]，那么这个数就应该分割cnt=a[i]/a[i+1]次，平分出来的数就是a[i]/(cnt+1)，特殊的是如果能a[i]能整除a[i+1]，那么整除次数要-1。

#include<bits/stdc++.h>
//#include<__msvc_all_public_headers.hpp>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
const ll MOD = 1e9 + 7;
int n;
ll a[N];
void init()
{
    
}
void solve()
{
    cin >> n;
    init();
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    ll ans = 0;
    for (int i = n - 1; i >= 1; i--)
    {
        if (a[i] > a[i + 1])
        {
            ll temp = a[i] / a[i + 1];//需要的分割次数
            if (a[i] % a[i + 1] == 0)
            {//整除时候少1
                temp--;
            }
            a[i] =  a[i]/ (temp+1ll);//平分出来的数
            ans += temp;
        }
    }
    cout << ans;
    cout << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}