蒟蒻贴一下某大佬的代码,问一下为什么最后输出是left-1而不是mid?
查看原帖
蒟蒻贴一下某大佬的代码,问一下为什么最后输出是left-1而不是mid?
463562
Dreamerlee✅楼主2021/2/2 12:13
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
inline long long read()//c++快速读入long long模板
{
	char ch = getchar();
	long long x = 0, f = 1;
	while (ch < '0' || ch > '9')
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}
int main(void)
{
	long long n, m, a[1010], sum, lon = 0, left = 0;//二分法
	long long mid;
	n = read(), m = read();
	for (int i = 1; i <= n; i++)
	{
		a[i] = read();
		lon = max(lon, a[i]);//找到最长的一棵树
	}
	while (left <= lon)
	{
		mid = (left + lon) / 2;//找中间值
		sum = 0;
		for (int i = 1; i <= n; i++)
		{
			if (mid > a[i])//如果锯子长度大于树高度,则不能得到木材
				continue;
			sum += abs(a[i] - mid);
		}
		if (sum >= m)
			left = mid + 1;
		else if (sum < m)
			lon = mid - 1;
	}
	cout << left - 1;
	return 0;
}

2021/2/2 12:13
加载中...