【CSP试题回顾】202303-2-垦田计划

本文主要是介绍【CSP试题回顾】202303-2-垦田计划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

CSP-202303-2-垦田计划

解题关键：二分查找

二分搜索是一种在有序数组中查找特定元素的高效算法。在本题中，二分搜索被用来找到能够在资源限制下完成所有任务的最短时间。这个时间在范围 k（不得少于这个天数）到 taskList[0].timeSpend（所有任务中耗时最长的一个，taskList是以基础耗时的降序顺序排列的容器）之间。

1. 初始化二分搜索的边界

左边界 (left)：设置为 k，因为根据问题描述，任务不能在少于 k 天的时间内完成。
右边界 (right)：设置为 taskList[0].timeSpend，即所有任务中耗时最长的一个，因为这是在没有任何资源限制的情况下可能需要的最大天数。

2. 进行二分搜索

二分搜索的核心思想是在每一步将搜索范围缩小一半。这是通过更新左边界或右边界来实现的，基于中间点 (mid) 的计算结果：

计算中间点 (mid)：在当前的左右边界内找到中间的天数，mid = left + (right - left) / 2。这是当前迭代我们要检查的天数。
检查给定天数是否可行 (canFinish 函数)：使用 canFinish 函数判断在给定的资源限制 m 下，是否能够将所有任务的完成时间缩短到 mid 天。这涉及到遍历所有任务，计算如果将它们缩短到 mid 天所需的总资源，并判断这是否超过了可用资源 m。

3. 更新搜索边界

如果 mid 天是可行的（即 canFinish(mid, m, taskList) 返回 true），这意味着我们可能还能找到更短的完成时间，同时满足资源限制。因此，我们尝试寻找更小的天数，将右边界 right 更新为 mid - 1。
如果 mid 天不可行，意味着我们需要更多的时间来完成所有任务，所以我们将左边界 left 更新为 mid + 1。

4. 终止条件

当 left 大于 right 时，二分搜索结束。此时，left 指向第一个不能满足条件的天数，而 right 指向最后一个能满足条件的天数。因为我们在搜索过程中一直在尝试找到更小的满足条件的天数，所以最终的答案应该是 left 或 right + 1（它们在循环结束时相等）。

解题思路

输入处理：
- 读取任务数量 n、可用资源 m 和目标完成天数 k。
- 初始化一个 taskList，然后读取每个任务的基础耗时和每天缩短需要的资源，将这些任务存入 taskList 中。
任务排序：
- 使用标准库函数 sort 对 taskList 进行排序，按照任务的基础耗时进行降序排列。这意味着耗时最长的任务会被放在列表的开始位置。
二分搜索初始化：
- 设置二分搜索的左边界 left 为目标完成天数 k，右边界 right 为任务中最长的基础耗时。设置 answer 为 right，表示初始假设最小可完成天数为最大耗时。
二分搜索执行：
- 进行二分搜索直到左边界 left 大于右边界 right。在每一步：
  - 计算中间值 mid 作为当前尝试的完成天数。
  - 调用 canFinish 函数，判断在 mid 天内是否可以在不超过资源 m 的条件下完成所有任务：
    - 如果可以（canFinish 返回 true），更新 answer 为 mid，并将搜索区间调整为左半部分，即 right 设置为 mid - 1，尝试寻找更小的可行天数。
    - 如果不可以（canFinish 返回 false），将搜索区间调整为右半部分，即 left 设置为 mid + 1，表示需要更多天数来完成任务。

完整代码

【100分-二叉搜索】

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;struct MyTask
{int timeSpend; // 基础耗时int resource; // 每缩短一天需要投入的资源
};int n, m, k;
vector<MyTask> taskList;// 检查是否可以在给定的天数和资源限制下完成所有任务
bool canFinish(int days, int m, vector<MyTask>& taskList) {int totalResourceNeeded = 0;for (const auto& task : taskList) {if (task.timeSpend > days) {totalResourceNeeded += (task.timeSpend - days) * task.resource;if (totalResourceNeeded > m) { // 如果所需资源超过了可用资源，则无法完成return false;}}}return true;
}int main() {cin >> n >> m >> k;for (int i = 0; i < n; i++){MyTask t;cin >> t.timeSpend >> t.resource;taskList.push_back(t);}// 按基础耗时进行排序sort(taskList.begin(), taskList.end(), [](const MyTask& a, const MyTask& b) {return a.timeSpend > b.timeSpend;});int left = k, right = taskList[0].timeSpend, answer = right;// 二分搜索while (left <= right) {int mid = left + (right - left) / 2;if (canFinish(mid, m, taskList)) {answer = mid; // 如果可以完成，则尝试找一个更小的天数right = mid - 1;}else {left = mid + 1; // 如果不可以完成，则需要更多的天数}}cout << answer;return 0;
}

【70分-暴力枚举】

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;struct MyTask
{int timeSpend; // 基础耗时int resource; // 每缩短一天需要投入的资源
};int n, m, k;
vector<MyTask>taskList;bool myCompare(const MyTask& a, const MyTask& b) // 自己定义比较函数
{if (a.timeSpend > b.timeSpend){return true;}return false;
}int main() {cin >> n >> m >> k;for (int i = 0; i < n; i++){MyTask t;cin >> t.timeSpend >> t.resource;taskList.push_back(t);}sort(taskList.begin(), taskList.end(), myCompare); // 按照基础耗时降序排列int timeSpendMax = taskList[0].timeSpend; // 最长的基础耗时for (int i = timeSpendMax - 1; i >= k; i--){int sumResourceSpend = 0; // 本轮消耗资源总和for (const auto& it : taskList) {if (it.timeSpend > i) // 可以缩减时间的任务{sumResourceSpend += (it.timeSpend - i) * it.resource;}}if (sumResourceSpend > m) // 消耗资源总和超过现有资源{cout << i + 1; // 输出上一轮的结果break;}else if (i == k) // 手中现有资源足够缩短至第k天{cout << k;break;}}return 0;
}