【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（它们在循环结束时相等）。

解题思路

1. 输入处理：

   • 读取任务数量 n、可用资源 m 和目标完成天数 k。
   • 初始化一个 taskList，然后读取每个任务的基础耗时和每天缩短需要的资源，将这些任务存入 taskList 中。

2. 任务排序：

   • 使用标准库函数 sort 对 taskList 进行排序，按照任务的基础耗时进行降序排列。这意味着耗时最长的任务会被放在列表的开始位置。

3. 二分搜索初始化：

   • 设置二分搜索的左边界 left 为目标完成天数 k，右边界 right 为任务中最长的基础耗时。设置 answer 为 right，表示初始假设最小可完成天数为最大耗时。

4. 二分搜索执行：

   • 进行二分搜索直到左边界 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;
}

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

【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;
}

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