蓝桥杯大学模拟赛(二) - 程序设计：植物大战僵尸题解

- 日理万妓 2022-12-28 14:15 150阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  输入描述
     *  输出描述
     *  数据范围
     *  输入
     *  输出
 *  算法分析
 *  算法过程
 *  代码

--------------------

# 题目描述 #

植物⼤战僵⼫为近来很⽕的⼀款游戏。⽽这⼀次我们不⼀样，我们要提前养成植物然后来抵抗僵 ⼫。

你的 `n` 个植物已经从左到右排成了⼀排，编号从 `1` 到 `n` ，起始的时候，他们的防御都是 `0` ，⽽你的 任务就是来提⾼他们的防御。

你⼀共有 `m` 天的时间进⾏备战，起始你在整个植物的最左边，每天你 **必须向左或向右**移动⼀格， 到达第 **ai** 棵植物的时候，你给这个植物增加 `m` 点的防御。

众所周知，根据⽊桶原理，整排植物的防御取决于最低防御的⼀棵植物，你想让 天以后的整排植 物的防御⼒最⾼，请问最⾼能是多少呢？

## 输入描述 ##

> 输入数据第一行包含以空格隔开的两个整数 **n,m**分别表示植物总数和你的备战天数
> 
> 第二行包含以空格隔开的 **n** 个整数 **a1.a2,…,an**，表示每次一个植物可以增加的防御力

## 输出描述 ##

> 输出⽂件共⼀⾏包括⼀个整数，表示整排植物可以达到的最⼤防御⼒

## 数据范围 ##

![1][]

## 输入 ##

4 8
    3 2 6 6

## 输出 ##

# 算法分析 #

**二分答案的防御力 + 贪心的去验证答案的正确性**

答案很明显是要求，防御力最大时的最小值。最大的最小问题可以想到使用二分法求解。

**二分答案，但是怎么验证这个答案是正确的呢？**

我们贪心的去看，每次都保证一个植物是在当前答案\*\*(mid变量)\*\*标准以上。

因此我们**让当前这个植物(a\[i\])和右边的植物(a\[i+1\])搭配来回走动（核心）**

所以当前植物会走\*\*⌈(a\[i\] / mid)⌉\*\* 次，右边植物会走\*\*⌈(a\[i\] / mid)⌉ - 1\*\*次

*  最后使得所有植物都到达**mid**标准以上时，计算总和天数，与m备战天数相比较验证答案

# 算法过程 #

![在这里插入图片描述][20201217185607685.gif_pic_center]

# 代码 #

#include <iostream>
    #include <cstdio>
    using namespace std;
    
    const int maxn = 1e5 + 7;
    long long n, m, mm, ans;
    long long a[maxn], d[maxn];
    
    //始终保证左边的数不低于p这个标准
    //用右边的数来回走动去保证左边这个数
    
    //二分答案的标准
    //去验证在这个标准下每个植物要踩多少次
    //与题目的天数去比较
    bool check(long long p)
    {
        
        long long sum = 0;  //总步数，即该标准下的天数
        long long temp = 0; //当前a[i]踩的步数
        long long tempn = 0; //用来记录搭配使得a[i]到达标准时，右边植物a[i+1]在搭配踩了多少步
        
        for (int i = 0; i < n; i++){
        
            if (p % a[i])
                temp = p / a[i] + 1;
            else
                temp = p / a[i];
            
            temp -= tempn;
            
            if (temp <= 0) {
            //说明搭配的位置在单独处理它之前，已经被踩到这个标准了
                if (i != n - 1) {
        
                    //因为每次要保证当前a[i]达到这个标准，所以最后一次会落在a[i]上
                    //但是此时a[i+1]已经达到标准了
                    //去处理a[i+2]的过程中会经过a[i+1]一次
                    //而当i == n - 1  时a[n-1] 后无元素要处理，所以不用经过a[n - 1]
                    temp = 1;
                }
                else{
        
                    temp = 0;
                }
                tempn = 0;  //右边并未搭配
            }
            else
                tempn = temp - 1;   //右边搭配的使用，只比当前这个少踩一次
            
            sum += temp + tempn;
            
            if (sum > m)
                return false;
        }
        return true;
    }
    
    int main()
    {
        
        scanf("%lld%lld", &n, &m);
        for (int i = 0; i < n; i++)
            scanf("%lld", &a[i]);
      
        long long l = 1, r = 1e18;  
        while (l <= r) {
        
            long long mid = (l + r) >> 1;
            
            if (check(mid)) {
        
                l = mid + 1;
                
            }
            else
                r = mid - 1;
        }
        
        printf("%lld\n", l - 1);
        
        return 0;
    }

[1]: /images/20221120/4d5aa58024fa41dfbcfd42f5e57914f2.png
[20201217185607685.gif_pic_center]: /images/20221120/b7b53e7f9d02491591532fc007c630a4.png