华为OD机试真题-不爱施肥的小布

题目描述:
某农场主管理了一大片果园，fields[i]表示不同果林的面积，单位:(m^2)，现在要为所有的果林施肥且必须在n天之内完成，否则影响收成。小布是果林的工作人员，他每次选择一片果林进行施肥，且一片果林施肥完后当天不再进行施肥作业。假设施肥机的能效为k，单位:(m^2lday)，请问至少租赁能效k为多少的施肥机才能确保不影响收成?如果无法完成施肥任务，则返回-1。
输入描述:
第一行输入为m和n, m表示 fields 中的元素个数，n表示施肥任务必须在n天内(含n天)完成;第二行输入为fields,fields[i]表示果林i的面积，单位:(m^2)
对于每组数据，输出最小施肥机的能效k，无多余空格。补充说明:
1 <= fields.length <= 10^41 <=n<=10^9
1<= fieldsil<=10^9

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

// 判断是否能在k天内完成施肥任务
bool canFinish(vector<long>& fields, int k, int n) {
	int days = 0;
	for (int i = 0; i < fields.size();i++ ) {
		if(fields[i]%k==0) days += fields[i] / k;
		else days += fields[i] / k + 1;
	}
	// 判断是否能在规定天数内完成施肥
	return days <= n;
}

int main() {
	int m;
	long n;
	cin >> m >> n;
	vector<long> fields(m);
	for (int i = 0; i < m; i++) {
		cin >> fields[i];
	}
	// 对果园按面积从大到小排序
	sort(fields.rbegin(), fields.rend());
	// 枚举最小的能效k，能在规定天数内完成施肥任务的最小值即为所求
	int left = 1, right = fields[0], ans = -1;
	while (left <= right) {
		long mid = left + (right - left) / 2;
		if (canFinish(fields, mid, n)) {
			ans = mid;
			right = mid - 1;
		}
		else {
			left = mid + 1;
		}
	}
	cout << ans << endl;
	return 0;
}