题解：CF1898B Milena and Admirer

Meickol · 2025-05-18 19:24:02 · 题解

思维 + 贪心

题意即每次操作可以选择一个位置，将这个位置的数拆分成两个正整数，显然拆分后的每个数只会比拆分前的数更小。

由于拆分后的数会变得更小，同时我们需要保证最终数列变为单调不降。显然从前往后正序遍历数组将无法保证当前位置拆分后是否满足整个序列单调不降，因此我们考虑贪心地从后往前倒序做，对于每次枚举到的位置，让其拆分出的数比后缀最小值小的同时尽可能地大。

考虑维护后缀最小值 mn。

• 当 a_i \le mn，无需操作，同时更新最小值 mn=a_i。
• 当 a_i \gt mn，令 k=\left \lceil \dfrac{a_i}{mn} \right \rceil，则需要对 a_i 这部分进行 k-1 次操作，并且更新最小的值为 \left \lfloor \dfrac{a_i}{k} \right \rfloor。

#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
typedef long long LL;
const int N=2e5+5;
int n;
int a[N];
void solve(){
    cin>>n;
    rep(i,1,n) cin>>a[i];
    int mn;
    memset(&mn,0x3f,sizeof mn);
    LL ans=0;
    per(i,n,1){
        if(a[i]<=mn) mn=a[i];
        else{
            int k=(a[i]+mn-1)/mn;
            ans+=k-1;
            mn=a[i]/k;
        }
    }
    cout<<ans;
}