Solution-P9889

· · 题解

题目链接

题目描述

有 n 个被冰车碾了的植物（初始高度为 0），种在 1 \sim n 的的位置，你初始处于戴夫家（位置为 0）。每步可以使自己的位置 +1 或 -1。求在走完 m 步后最小植物高度的最大值。

题目分析

求最小值的最大值的题目大概率都是二分答案。

然而确实是，让我们分析一下如何二分。显然答案具有单调性，若最小植物高度最大值为 x，那么小于 x 的数也一定能达到。所以选择二分 x。其中下界为 0，上界为 LONG_LONG_MAX，当然你设置一些其他的数字也可以。

接下来我们创建一个 b 数组，表示第 i 个植物需要浇 b_i 次水才可以达到 mid，设 b_i=\Large\lceil\frac{a_i}{mid}\rceil。那么很显然，最优解便是使位置不断 +1 再 -1。因此对于每棵植物，如果其还没有走到足够的步数，那么便将总步数增加 b_i \times 2+i-u-2，同时将 b_{i+1}\gets b_{i+1}-b_i+1，其中 u 为上一个没有走到足够步数的点，而减少的两步目的是减少走完后多走的 1 次，i-u 为两个无需浇水之间点的距离。

代码

在过程中 ans 有可能超过 long long 范围，所以应该在 ans>m 时立刻退出循环，同样也可以优化时间复杂度，其余代码在前文均有提及。

时间复杂度 O(Tn \log q)，其中 q 为二分上界，空间复杂度 O(n)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,m,a[114514],b[114514],l,r,mid,ans,u;
bool flag;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        flag=true;
        l=0;
        r=LONG_LONG_MAX;
        while(l<=r){
            mid=(l+r)>>1;
            ans=u=0;
            flag=true;
            for(int i=1;i<=n;i++){
                b[i]=ceil(1.0*mid/a[i]);
            }
            for(int i=1;i<=n;i++){
                if(b[i]>0){
                    ans+=i-u-2+(b[i]<<1);
                    u=i;
                    b[i+1]-=b[i]-1;
                }
                if(ans>m){
                    flag=false;
                    break;
                }
            }
            flag?l=mid+1:r=mid-1;
        }
        cout<<l-1<<'\n';
    }
    return 0;
}