关键点：二分查找
在这个问题中，有一系列的田地需要在特定的时间 t i t_i ti 之后开垦，每块田地的开垦成本为 c i c_i ci。目标是确定最早的一天，使得在不超过给定的资源 m m m 的情况下，可以开始开垦所有田地。
1.暴力枚举
- 时间复杂度是 O ( N ) × N O(N) \times N O(N)×N，其中 N N N 是时间范围的大小，因为它需要逐一检查每一天，直到找到满足条件的一天。在最坏的情况下，这意味着可能需要检查所有的天数。
2.二分查找
- 时间复杂度是 O ( l o g N ) × N O(logN) \times N O(logN)×N，这里的 N N N 也是时间范围的大小。二分查找通过每次排除一半的搜索范围来缩小可能的解空间，因此搜索所需的步骤数量是对数级别的。这在大范围搜索时显著减少了计算量。
通过二分查找，我们能够有效减少必要的计算步骤，从而快速定位到满足条件的最早开始开垦的时间。与暴力枚举相比，二分查找大幅减少了所需的时间，特别是在可能的时间范围很大时，这种时间复杂度的优化尤为显著。
解题思路
-
初始化变量： 农田数量 n n n，可用资源 m m m，开垦一块区域的最少天数 k k k，最大时间点
maxTi（初始设为-1），天数列表dayList和农田列表feildList。每块农田用一个结构体feild来表示，包括开垦时间点ti和成本ci。 -
读入数据/构建搜索范围： 在
main函数中，代码读取农田数量、可用资源、开始时间，并为每块农田读取开垦时间和成本，同时更新最大开垦时间maxTi。根据农田的开垦时间点生成一个时间列表dayList，这个列表从开垦一块区域的最少天数k到最大时间maxTi。这个列表代表可能的完成开垦的所有天数。 -
二分搜索： 使用二分搜索找出最小的满足条件的时间。在
binarySearch函数中，设置左右边界left和right，并通过迭代减少搜索范围来找到最早的一天，从那一天开始，可以在不超出资源 m m m 的情况下完成所有农田的开垦。这是通过计算每一天剩余需要开垦的农田所需的总成本sumDay来判定的。 -
检查条件： 在二分搜索过程中，每次计算中间点
mid的资源总和sumRes。如果sumRes > m，说明资源不足，需要推迟开垦时间（即增大left）。如果sumRes <= m，则检查是否可以将时间提前（即减小right）。特别的，当sumRes <= m且下一天（mid - 1）所需资源超过m或mid等于起始时间k时，找到了满足条件的最早时间，此时输出该时间并结束搜索。 -
输出结果： 当找到满足条件的最早时间时，即在不超出预算的情况下，最早可以完成所有农田开垦的时间，输出这一天。
完整代码
【100分思路-二分查找】
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct feild
{
long long ti, ci;
};
long long m, n, k, maxTi = -1;
vector<long long>dayList;
vector<feild>feildList;
long long sumDay(int t) {
long long sumResource = 0;
for (auto& it : feildList)
{
if (t < it.ti)
sumResource += (it.ti - t) * it.ci;
}
return sumResource;
}
void binarySearch(vector<long long>& arr) {
long long left = 0;
long long right = arr.size() - 1;
while (left <= right) {
long long mid = left + (right - left) / 2; // 避免溢出
long long sumRes = sumDay(mid);
if (sumRes > m) {
left = mid + 1; // 调整左边界
}
else if (sumRes <= m) {
right = mid - 1; // 调整右边界
}
if ((sumRes <= m && sumDay(mid - 1) > m) || mid == k) // 终止条件
{
cout << mid;
return;
}
}
}
int main() {
cin >> n >> m >> k;
feildList.resize(n);
for (size_t i = 0; i < n; i++)
{
cin >> feildList[i].ti >> feildList[i].ci;
maxTi = max(maxTi, feildList[i].ti);
}
for (size_t i = k; i <= maxTi; i++)
{
dayList.push_back(i);
}
binarySearch(dayList);
return 0;
}
【70分思路-暴力枚举】
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct feild
{
int ti, ci;
};
int m, n, k, maxTi = -1;
int main() {
cin >> n >> m >> k;
vector<feild>feildList(n);
for (size_t i = 0; i < n; i++)
{
cin >> feildList[i].ti >> feildList[i].ci;
maxTi = max(maxTi, feildList[i].ti);
}
for (size_t i = k; i < maxTi; i++)
{
long long sumResource = 0;
for (auto& it : feildList)
{
if (i < it.ti) sumResource += (it.ti - i) * it.ci;
}
if (sumResource <= m)
{
cout << i;
break;
}
}
return 0;
}