C++分治算法------ 砍树

2023-11-05 10:04
文章标签 算法 c++ 分治 ------ 砍树

本文主要是介绍C++分治算法------ 砍树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

伐木工人 Mirko 需要砍M米长的木材。对 Mirko 来说这是很简单的工作,因为他有一个漂亮的新伐木机,可以如野火一般砍伐森林。不过,Mirko 只被允许砍伐一排树。

Mirko 的伐木机工作流程如下:Mirko 设置一个高度参数H(米),伐木机升起一个巨大的锯片到高度H,并锯掉所有树比 高H的部分(当然,树木不高于H 米的部分保持不变)。Mirko 就得到树木被锯下的部分。

例如,如果一排树的高度分别为20,15,10和17,Mirko 把锯片升到15米的高度,切割后树木剩下的高度将是 15,15,10 和15,而 Mirko 将从第1棵树得到5米,从第4棵树得到2米,共得到7米木材。

Mirko 非常关注生态保护,所以他不会砍掉过多的木材。这也是他尽可能高地设定伐木机锯片的原因。请帮助 Mirko 找到伐木机锯片的最大的整数高度H,使得他能得到的木材至少为M米。换句话说,如果再升高1米,他将得不到H米木材。

输入格式

第1行2个整数N和M,N 表示树木的数量,M 表示需要的木材总长度。

第2行N个整数表示每棵树的高度。

输出格式

输出共1个整数,表示锯片的最高高度。

样例
输入样例1
4 7
20 15 10 17
输出样例1
15
输入样例2
5 20
4 42 40 26 46
输出样例2
36

代码:

#include<bits/stdc++.h>
using namespace std;
long long n,m,tmp,l,r,mid,ans;
const long long N=1000010;
long long a[N];
bool check(int x){for(long long i=1;i<=n;i++){ if(x<a[i])tmp+=a[i]-x;}return m<=tmp; 
}
int main(){cin>>n>>m;for(long long i=1;i<=n;i++){cin>>a[i];r=r>a[i]?r:a[i];}while(l<=r){tmp=0;long long mid=(l+r)>>1;if(check(mid))l=(ans=mid)+1;else r=mid-1;}cout<<ans;return 0;
} 

这篇关于C++分治算法------ 砍树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/349113

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if(staticif),:本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程