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

2023-12-13 11:39:06

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;
}

文章来源:https://blog.csdn.net/ashbringer233/article/details/134965331
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。