CF1898B Milena and Admirer

xinruian · 2023-11-29 17:47:09 · 题解

题意

给你一个数组 a，每次操作你可以把数组中任意一个元素 a[i] 分解为正整数 x 和 y（要求 x+y=a[i]），求把数组 a 变为非递减数组的最小操作数。

思路

首先我们要明确：把一个数 num 分成 k 个数时，需要对 num 进行 k-1 步操作。下面来分析一下这道题。

这是一道贪心题。我们倒着遍历这个数组，如果当前遍历到的数 a[i] 比他后面的数 b 要大，为了让操作数最小，那么该数一定要拆分成 \lceil \frac{a[i]}{b} \rceil 份(记为 x），拆分出的数字的最小值为 \lfloor \frac{a[i]}{x} \rfloor 。

下面来解释一下，比如数组 [7,3]，那么把 7 分成 2 个数是不够的，要把其分为 3 个数，我们平均的分解这个数可以使得分解的数中最小的数尽可能的大，所以分解为 [2,2,3]，最小的数是 2，即 \lfloor \frac{7}{3} \rfloor。

代码

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <unordered_map>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10;
int a[N];

void solve() {
    int n;
    cin >> n;
    long long ans = 0;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    int b = a[n];
    for (int i = n - 1; i; i --) 
        if (a[i] > b) 
        {
            int k = (a[i] - 1) / b;
            ans += k;
            b = a[i] / (k + 1);
        }
        else
            b = a[i];
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t --)
        solve();
    return 0;
}