校门内的树

题目描述

\(FZYZ\)城门的左侧有一排 \(n\) 棵树木。它们按照距离的远近排列，第 1 棵树的高度为\(a_1\)米，第 2 棵树木的高度为 \(a_2\) 米，第 3 棵树木的高度为 \(a_3\)米，……，第 \(n\) 棵树木的高度为 \(a_n\)米。

为了给同学们以积极向上的感觉，一些同学自发地决定对树木进行修剪，使得树木呈现上升的趋势。具体地说，他们希望对树木进行修剪和整理，使得修剪之后的树木高度 \(b_1,b_2,b_3,...,b_n\) 米且满足 \(b_1<b_2<b_3<...<b_n\)。
他们不仅可以对较高的枝条进行修剪使其高度减小，还可以通过枝条的加固使得树木的高度增加，而且可以使树木的高度减小和增加任意的高度，但一定得是整数（单位为米），而且最后树的高度必须大于零。然而，树木的整理只能在课间进行，因此他们没有太多的时间。对于一棵树，将其修剪使其高度减少 \(x\) 米需要花费 \(x\) 分钟的时间，将其整理加固使其高度增加 \(x\) 米也需要花费 \(x\) 分钟的时间。

参加这次活动的同学超过 \(n\) 个，因此所有树木可以同时得到修剪或整理。请你帮他们求出，最少要花费多少的时间可以修剪使得树木递增。注意：花费的总时间取决于最后完成修剪或整理的同学。

输入格式

输入文件的第一行包含 \(1\) 个整数 \(n\)，表示树木的个数。
输入文件的第二行包含 \(n\) 个整数 \(a_1\),\(a_2\),\(a_3\),...,\(a_n\)，表示第 \(1\) 棵树的高度、第 \(2\) 棵树的高度、第 \(3\) 棵树的高度、……、第 \(n\) 棵树的高度。

输出格式

输出文件的第一行包含一个整数，表示能修剪使得树木具有“向上的趋势”的最短时间。

输入输出样例

输入样例1

3
9 5 11

输出样例1

3

输入样例2

2
5 8

输出样例2

0

输入样例3

5
1 1 1 1 1

输出样例3

4

输入样例4

5
548 47 58 250 2012

输出样例4

251

样例解释

样例解释1

在样例 \(1\) 中，可以把第 \(1\) 棵树花费 \(2\) 分钟降低 \(2\) 米，第 \(2\) 棵树花费 \(3\) 分钟增加 \(3\) 米，总共花费 \(3\) 分钟，最终的高度分别为 7\(m\),8\(m\),11\(m\)；

样例解释2

在样例 \(2\) 中，原来的树就已经呈现了上升的趋势，因此不需要进行修剪或整理，所需要的时间为 \(0\) 分钟；

样例解释3

在样例 \(3\) 中，可以把第 \(2\) 棵树花费 \(1\) 分钟增加 \(1\) 米，第 \(3\) 棵树花费 \(2\) 分钟增加 \(2\) 米，第 \(4\) 棵树花费 \(3\) 分钟增加 \(3\) 米，第 \(5\) 棵树花费 \(4\) 分钟增加 \(4\) 米，总共花费 \(4\) 分钟，最终的高度分别为 1\(m\),2\(m\),3\(m\),4\(m\),5\(m\)。

数据范围

对于 \(40\%\) 的数据，\(n \leq 2；\)
对于 \(60\%\) 的数据，\(n \leq 15；\)
对于 \(80\%\) 的数据，\(a_i \leq 3000；\)
对于 \(100\%\) 的数据，\(n \leq 50,a_i \leq10^9\)

分析

“最少要花费多少的时间可以修剪使得树木递增。注意：花费的总时间取决于最后完成修剪或整理的同学。”，得知本题为求“最大值最小”的问题，考虑用二分答案求解。答案满足二分性质，如下图所示：

最终的 \(right\) 即为所求。那么对于二分出的一个答案 \(x\)，如何检查其是否符合题目要求呢？考虑使用贪心法，将原来的树木高度记在 \(a\) 数组中，第 \(i\) 棵树高 \(a[i]\)，修剪后的高度记录在\(b\)数组中。对于第一棵树，我们希望他尽量修建得矮一些会更优。因此，如果 \(a[1]-x>1\) ,则 \(b[1]=a[1]-x\) ,否则将第一棵树修剪到高度为\(1\)（高度必须是大于零的整数，最小为1）。从第二棵树开始，\(O(n)\) 遍历一遍处理所有树，如果当前树增高 \(x\) 也还不比前一棵树高，则返回 \(false\)。否则让当前树尽量剪得矮一些(但要至少比前一棵树高\(1\))会更优：即如果\(a[i]-x<b[i-1]+1\)，则\(b[i]=b[i-1]+1\),否则，\(b[i]=a[i]-x\);

时间复杂度为\(O(n\log\{max\ a_i\})\)。可以通过本题全部数据。

Sample Code

#include<cstdio>
#include<cstring>
int a[60],b[60];
int max,n;
using namespace std;
bool check(int x)
{
    if(x<0) return 0;
    b[1]=a[1]-x>1?a[1]-x:1;
    for(int i=2;i<=n;i++)
    {
        if(a[i]+x<=b[i-1]) return 0;
        b[i]=a[i]-x<b[i-1]+1?b[i-1]+1:a[i]-x;
    }
    return 1;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        max=a[i]>max?a[i]:max;
    }
    int right=max+10,left=-1,mid;
    while(right-left>1)
    {
        mid=(right+left)/2;
        if(check(mid)) right=mid;
        else left=mid;
    }
    printf("%d\n",right);
    return 0;
}

辛辛苦苦写完，看完点个赞呗！