洛谷 砍树

第一种常规做法：

二分：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
int q[N], n, m;
int check(int x)
{
	long long sum = 0;
	for (int i = 0; i < n; ++i)
	{
		if (x < q[i])
		sum += q[i] - x;
	}
	if (sum >= m) return 1;//这里不能写sum <= m
	else return 0;         
}
int search2(int l, int r)
{
	while (l < r)
	{
		int mid = l + r + 1 >> 1;
		if (check(mid)) l = mid;
		else r = mid - 1;
	}
	return l;
}
int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; ++i) scanf("%d", &q[i]);
	sort(q, q + n, greater<int>()); //从高到低排序，则q[0]为最大值
	printf("%d", search2(0, q[0]));//二分查找0到q[0]
	return 0; 
}

二分有两个模板来处理边界值，但这题不可以像下面这样写：

int check(int x)
{
	long long sum = 0;
	for (int i = 0; i < n; ++i)
	{
		if (x < q[i])
		sum += q[i] - x;
	}
	if (sum <= m) return 1;
	else return 0;         
}
int search2(int l, int r)
{
	while (l < r)
	{
		int mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	return l;
}

因为很大可能不存在sum=m的情况，比如m = 7, 但sum没有等于7的，那么sum往下取，比如取6， 那么sum取小了，x就取大了。本题需要向上取。

总的来说，二分的结果是最接近check性质的那个。

比如sum的值可取 12 11 10 9 8      6 5 4 3 2 1

                              <---------------   7  -------------->

m = 7,

如果是sum>=m,最终二分的结果是取到sum=8所对应的高度，

如果是sum<=m,最终二分的结果是取到sum=6所对应的高度。

（二分的对象要有序，比如从低到高，或从高到低（如上面的sum），不可以杂乱无章。）

先根据题意找到需要的check性质，再写二分，然后相应的带入适合的模板修改二分代码。

第二种：

看的洛谷的第一个题解的思路，自己写的代码。（思路不是我想的）

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
int main()
{
	int n, m , ans;
	int q[N];
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; ++i) scanf("%d", &q[i]);
	sort(q, q + n);  //由低到高排序
	long long sum = 0;  //long long 防溢出
	int a = n - 1;
	int b = 1;
	while (sum < m)
	{
		sum += (q[a] - q[a - 1]) * b;
		a --;
		b ++; 
	} 
	ans = q[a] + (sum - m) / (b - 1);
	printf("%d", ans);
	return 0; 
}

 （第一次写，有点乱）