二叉树的结点数怎么算_二叉树的结点数怎么算[通俗易懂]

题目链接：https://www.luogu.com.cn/problem/P1873

题目描述：

    伐木工人米尔科需要砍倒 M 米长的木材。这是一个对米尔科来说很容易的工作，因为他有一个漂亮的新伐木机，可以像野火一样砍倒森林。
    米尔科的伐木机工作过程如下：米尔科设置一个高度参数 H（米），伐木机升起一个巨大的锯片到高度 H，并锯掉所有的树比 H 高的部分（当然，树木不高于 H 米的部分保持不变）。米尔科就得到树木被锯下的部分。
    例如，如果一行树的高度分别为20，15，10 和17，米尔科把锯片升到 15 米的高度，切割后树木剩下的高度将是15，15，10 和 15，而米尔科将从第 1 棵树得到 5 米，从第 4 棵树得到 2 米，共得到 7 米木材。
    米尔科非常关注生态保护，所以他不会砍掉过多的木材。这正是他为什么尽可能高地设定伐木机锯片的原因。帮助米尔科找到伐木机锯片的最大的整数高度 H，使得他能得到木材至少为 M米。换句话说，如果再升高 1 米，则他将得不到 M 米木材。

输入格式：

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

输出格式：

1个整数，表示砍树的最高高度。

输入输出样例：

输入 #1                                                              

5 20
4 42 40 26 46

输出 #1

36

说明：1 ≤ N ≤ 10^6，1 ≤ M ≤ 2×10^9 ，每棵树的高度 < 10^9，所有木材长度值和>M。

 题目分析：

锯片的高度为H，树木超过H部分的会被砍掉，不足的将不变，H在变小的同时所砍伐的木头数量也会随之变大呈单调关系，且题目所规定的数据范围较大，如果直接暴力枚举的话应该会超时，因此可以尝试使用二分法来做这道题。

二分法就是求极值的方法，通常已知答案的取值范围，然后每次取取值范围的中点，判断其是否可行，然后对可行的一半再进行处理。（PS：二分法一定要注意边界的取值才能保证在正确的范围内尽可能的求最优解）

分析可得这道题用二分的左边界的初始值为1，右边界的初始值为最高的树的高度，树的高度我用了数组来储存，最后答案应该输出右边界（锯片的最大高度）。题目数据范围较大，因此定义时用long long 而不是 int !!!

二分思路如下：

#include<iostream>
using namespace std;
long long h[1000001];//储存树的高度
long long N, M, L, R, mid;//L和R分别为二分的左边界和右边界
void check(long long N, long long R,long long M)
{
	long long L = 1;
	while (L <= R)
	{
		mid = (L + R) / 2;
		long long x = 0;
		for (int i = 1; i <= N; i++)
			if (h[i] > mid)
				x += h[i] - mid;
		if (x < M)
			R = mid - 1;
		else
			L = mid + 1;
	}
}

整体代码如下（已AC）：

#include<iostream>
#include<algorithm>
using namespace std;
long long h[1000001];//储存树的高度
long long N, M, L, mid;
int main()
{
	int i;
	cin >> N >> M;//输入树的数量N和所需的木材总长度
	for (i = 1; i <= N; i++)
	{
		cin >> h[i];
	}
	sort(h, h + N + 1);//将所有树木进行排序，以便找到最高的树
	L = 1;//左边界
	long long max = h[N];//右边界
	while (L <= max)
	{
		mid = (L + max) / 2;
		long long x = 0;//每个测试案例中木材的总长度
		for ( i = 1; i <= N; i++)
			if (h[i] > mid)
				x += h[i] - mid;
		if (x < M)//测试案例中的木材总长度小于需求量
			max = mid - 1;//右边界改变，降低锯片高度以增加所砍木材总长度
		else//超过则改变左边界，以提高锯片高度
			L = mid + 1;
	}
	cout << max;//输出锯片的最大高度
	return 0;
}

 由于我数组下标从1开始，因此我定义数组时多了1位，我查找最高的树时用了sort排序，排序中的实参也要增加1位。

比较简单基础的一道二分题，如有不足的地方可以讨论讨论。

计算机204 zjr

今天的文章二叉树的结点数怎么算_二叉树的结点数怎么算[通俗易懂]分享到此就结束了，感谢您的阅读。