【CSP试题回顾】202303-2-垦田计划（优化）

CSP-202303-2-垦田计划

关键点：二分查找

在这个问题中，有一系列的田地需要在特定的时间 $t_i$ 之后开垦，每块田地的开垦成本为 $c_i$。目标是确定最早的一天，使得在不超过给定的资源 $m$ 的情况下，可以开始开垦所有田地。

1.暴力枚举

• 时间复杂度是 $O(N)\times N$，其中 $N$ 是时间范围的大小，因为它需要逐一检查每一天，直到找到满足条件的一天。在最坏的情况下，这意味着可能需要检查所有的天数。

2.二分查找

• 时间复杂度是 $O(logN)\times N$，这里的 $N$ 也是时间范围的大小。二分查找通过每次排除一半的搜索范围来缩小可能的解空间，因此搜索所需的步骤数量是对数级别的。这在大范围搜索时显著减少了计算量。

通过二分查找，我们能够有效减少必要的计算步骤，从而快速定位到满足条件的最早开始开垦的时间。与暴力枚举相比，二分查找大幅减少了所需的时间，特别是在可能的时间范围很大时，这种时间复杂度的优化尤为显著。

解题思路

1. 初始化变量： 农田数量 $n$，可用资源 $m$，开垦一块区域的最少天数 $k$，最大时间点 maxTi（初始设为-1），天数列表 dayList 和农田列表 feildList。每块农田用一个结构体 feild 来表示，包括开垦时间点 ti 和成本 ci。

2. 读入数据/构建搜索范围： 在 main 函数中，代码读取农田数量、可用资源、开始时间，并为每块农田读取开垦时间和成本，同时更新最大开垦时间 maxTi。根据农田的开垦时间点生成一个时间列表 dayList，这个列表从开垦一块区域的最少天数 k 到最大时间 maxTi。这个列表代表可能的完成开垦的所有天数。

3. 二分搜索： 使用二分搜索找出最小的满足条件的时间。在 binarySearch 函数中，设置左右边界 left 和 right，并通过迭代减少搜索范围来找到最早的一天，从那一天开始，可以在不超出资源 $m$ 的情况下完成所有农田的开垦。这是通过计算每一天剩余需要开垦的农田所需的总成本 sumDay 来判定的。

4. 检查条件： 在二分搜索过程中，每次计算中间点 mid 的资源总和 sumRes。如果 sumRes > m，说明资源不足，需要推迟开垦时间（即增大 left）。如果 sumRes <= m，则检查是否可以将时间提前（即减小 right）。特别的，当 sumRes <= m 且下一天（mid - 1）所需资源超过 m 或 mid 等于起始时间 k 时，找到了满足条件的最早时间，此时输出该时间并结束搜索。

5. 输出结果： 当找到满足条件的最早时间时，即在不超出预算的情况下，最早可以完成所有农田开垦的时间，输出这一天。

完整代码

【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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

【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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34