2023.09.27-秋招-第三题-运货

TaZi SU @ 8 months ago

题面描述

在这个问题中，有 $m$ 个集装箱和 $n$ 个叉车，叉车的载重量需大于等于集装箱的重量才能运输。还有 $x$ 个增强组件，每个组件可以让叉车的载重量增加 $y$ ，但每个叉车最多只能使用一个组件。目标是计算出最多能运输多少个集装箱。输入包括集装箱重量和叉车载重量的信息，输出为最大可运输的集装箱数量。

思路：二分答案 + 贪心算法

原题链接：2071. 你可以安排的最多任务数目 - 力扣（LeetCode）

这个问题可以通过二分答案和贪心算法来解决。我们的目标是找到最大的集装箱数量

首先，我们对叉车和集装箱按照重量进行排序。这样我们可以保证每次都是最轻的叉车去运送最轻的集装箱。

然后，我们使用二分答案来找到最大的满足条件的集装箱数量。我们设定一个范围，最小值为-1（表示没有一个集装箱可以被运送），最大值为m和n的最小值加1（表示所有的集装箱都可以被运送）。

在二分查找的每一步，我们都会尝试一个中间的集装箱数量，然后检查是否所有的叉车都能在使用增强组件的情况下运送这么多的集装箱。我们使用一个check函数来进行这个检查。

check函数会遍历所有的叉车，对于每一个叉车，如果它的载重量大于等于当前的集装箱的重量，那么它就可以运送这个集装箱，我们就将这个集装箱从列表中移除。否则，我们就需要使用一个增强组件来增加叉车的载重量。我们使用二分搜索来找到一个可以使叉车的载重量大于等于当前集装箱重量的增强组件。如果我们找到了这样的增强组件，我们就将它从列表中移除，然后继续下一个叉车。如果我们没有找到这样的增强组件，或者增强组件已经用完了，那么我们就返回False，表示当前的集装箱数量不满足条件。

如果check函数返回True，表示当前的集装箱数量满足条件，我们就尝试增大集装箱数量。否则，我们就尝试减小集装箱数量。
当我们找到了最大的满足条件的集装箱数量，我们就输出这个数量。

题解

我们的问题可以使用二分答案结合贪心算法来求解，目标是找到能够运输的最大集装箱数量。

数据结构准备：首先，我们将叉车和集装箱的重量进行排序。通过排序，我们可以确保在每一步中，最轻的叉车去尝试运输最轻的集装箱，这样可以提高运输的效率。
二分查找：我们设定二分查找的范围，最小值为-1（表示没有一个集装箱可以被运送），最大值为 $m$ 和 $n$ 的最小值加1（表示理论上所有的集装箱都可以被运送）。在每次查找中，我们尝试一个中间值作为当前集装箱的数量。
检查函数：我们定义一个check函数来验证在当前设定的集装箱数量下，是否能找到足够的叉车进行运输。函数的逻辑如下：
- 遍历每个集装箱，尝试为其找到一个合适的叉车。
- 如果叉车的载重量能够满足集装箱的重量，则该叉车可以运送该集装箱。
- 如果叉车不能直接运送该集装箱，则尝试使用增强组件来提升叉车的载重量。
- 通过线性搜索来找合适的叉车，如果未能找到合适的叉车，则返回False。
调整二分查找范围：如果check函数返回True，则表示当前的集装箱数量可以满足条件，我们尝试增加集装箱数量；如果返回False，则减少集装箱数量。
输出结果：最终输出满足条件的最大集装箱数量。

时间复杂度

$O(nlogm)$

代码

C++

#include <bits/stdc++.h>

using namespace std;

int m, n, x, y; // m: 集装箱数量, n: 叉车数量, x: 增强组件数量, y: 增强重量
int weight[50005]; // 存储集装箱的重量
int load[50005]; // 存储叉车的载重量

bool is_get[50005]; // 用于标记叉车是否被使用

// 检查是否能运送当前数量的集装箱
bool check(int m, int n, int cur_res) {
    int cur_x = 0; // 当前使用的增强组件数量
    vector<int> weight_copy(weight, weight + cur_res); // 当前需要运输的集装箱
    vector<int> load_copy(load + n - cur_res, load + n); // 当前可用的叉车

    // 从重到轻遍历集装箱
    for (int i = weight_copy.size() - 1; i >= 0; --i) {
        bool is_find = false; // 标记当前集装箱是否找到叉车
        // 查找一个合适的叉车直接运输集装箱
        for (int j = 0; j < load_copy.size(); ++j) {
            if (weight_copy[i] <= load_copy[j]) { // 叉车可以直接运输集装箱
                load_copy.erase(load_copy.begin() + j); // 使用该叉车
                is_find = true; // 找到叉车
                break;
            }
        }
        // 如果未找到，尝试使用增强组件
        if (!is_find) {
            for (int j = 0; j < load_copy.size(); ++j) {
                if (weight_copy[i] <= load_copy[j] + y && cur_x < x) { // 使用增强组件后可以运输
                    load_copy.erase(load_copy.begin() + j); // 使用该叉车
                    cur_x++; // 增加使用的增强组件数量
                    is_find = true; // 找到叉车
                    break;
                }
            }
        }
        // 如果仍未找到合适的叉车，返回 false
        if (!is_find)
            return false;
    }
    return true; // 找到所有集装箱的合适叉车
}

int main() {
    int res = 0; // 最终结果
    cin >> m >> n >> x >> y; // 输入集装箱数量、叉车数量、增强组件数量和增强重量
    for (int i = 0; i < m; ++i) {
        cin >> weight[i]; // 输入每个集装箱的重量
    }
    for (int i = 0; i < n; ++i) {
        cin >> load[i]; // 输入每个叉车的载重量
    }

    // 对集装箱和叉车的重量进行排序
    sort(weight, weight + m);
    sort(load, load + n);

    // 二分查找的范围
    int left = 1, right = min(m, n); // 集装箱数量的范围
    while (left <= right) {
        int mid = left + (right - left) / 2; // 中间值
        // 检查是否能运输 mid 个集装箱
        if (check(m, n, mid)) {
            res = mid; // 更新结果
            left = mid + 1; // 尝试运输更多的集装箱
        } else {
            right = mid - 1; // 尝试运输更少的集装箱
        }
    }
    cout << res << endl; // 输出结果
    return 0;
}

python代码

from sortedcontainers import SortedList  # 引入SortedList库，用于维护有序列表（此行代码未使用）
import bisect  # 引入bisect库，用于二分查找操作

# 定义检查函数
def check(ts, ws):
    p, s = pills, strength  # 将增强组件数量和增强力量分别赋值给p和s
    for i in range(len(ws)):  # 遍历所有叉车
        if ws[i] >= ts[0]:  # 如果叉车的载重量大于等于当前最轻集装箱的重量
            ts.pop(0)  # 直接使用该叉车运送该集装箱
        else:
            # 查找在增强后可以运输的集装箱的索引
            idx = bisect.bisect_right(ts, ws[i] + s)
            if idx == 0 or p == 0:  # 如果没有可用的集装箱，或者增强组件用完
                return False  # 返回False，表示无法运输
            p -= 1  # 使用一个增强组件
            ts.pop(idx - 1)  # 移除能运送的集装箱
    return True  # 如果所有叉车都能运输集装箱，返回True

# 输入集装箱数量、叉车数量、增强组件数量和增强重量
m, n, pills, strength = list(map(int, input().split()))
# 输入每个集装箱的重量
tasks = list(map(int, input().split()))
# 输入每个叉车的载重量
workers = list(map(int, input().split()))

# 对集装箱和叉车的重量进行排序
tasks.sort()
workers.sort()

# 设置二分查找的范围
lo, hi = -1, min(m, n) + 1
while lo + 1 < hi:  # 当low小于high时，进行二分查找
    mid = (lo + hi) // 2  # 计算中间值
    # 检查是否可以运输mid个集装箱
    if check(tasks[:mid], workers[n - mid:n]):
        lo = mid  # 可以运输，尝试增加集装箱数量
    else:
        hi = mid  # 不能运输，减少集装箱数量

# 输出最大可运输的集装箱数量
print(lo)

Java代码

import java.util.*; // 导入Java集合类库

public class Main {
    static int m; // 货物的数量
    static int n; // 卡车的数量
    static int x; // 拖斗的数量
    static int y; // 每个拖斗的载重量
    static int[] weights; // 每个货物的重量
    static int[] loads; // 每个卡车的载重量

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // 创建输入扫描器
        m = sc.nextInt(); // 输入货物数量
        n = sc.nextInt(); // 输入卡车数量
        x = sc.nextInt(); // 输入拖斗数量
        y = sc.nextInt(); // 输入每个拖斗的载重
        weights = new int[m]; // 初始化货物重量数组
        for (int i = 0; i < m; i++) weights[i] = sc.nextInt(); // 输入每个货物的重量
        loads = new int[n]; // 初始化卡车载重量数组
        for (int i = 0; i < n; i++) loads[i] = sc.nextInt(); // 输入每个卡车的载重
        sc.close(); // 关闭扫描器

        // 将货物按重量升序排序
        Arrays.sort(weights);
        // 将卡车按载重量升序排序
        Arrays.sort(loads);

        // 使用贪心算法和二分查找
        int left = 0, right = m; // 设置二分查找的范围
        while(left < right) {
            int mid = (left + right + 1) >> 1; // 计算中间值
            if(check(mid)) { // 检查是否能运输mid个集装箱
                left = mid; // 可以运输，尝试增加集装箱数量
            } else {
                right = mid - 1; // 不能运输，减少集装箱数量
            }
        }
        System.out.println(left); // 输出最大可运输的集装箱数量
    }

    // 检查在当前设定的集装箱数量下是否能运输
    public static boolean check(int mid) {
        if (mid > n) return false; // 如果货物数量大于卡车数量，返回false

        // TreeMap自动排序（默认按key升序排序），存储卡车载重量及其数量
        TreeMap<Integer, Integer> map = new TreeMap<>();
        // 将可以使用的卡车载重存入map
        for (int i = n - mid; i < n; i++)
            map.compute(loads[i], (k, v) -> (v == null ? 1 : v + 1)); // 更新卡车数量

        // 从重到轻遍历货物
        int t = x; // 当前可用的拖斗数量
        for (int i = mid - 1; i >= 0; i--) {
            int weight = weights[i]; // 当前货物重量
            Map.Entry<Integer, Integer> en = map.lastEntry(); // 获取map中载重量最大的卡车
            if (en.getKey() >= weight) { // 如果卡车可以运输该货物
                map.compute(en.getKey(), (k, v) -> (v <= 1 ? null : v - 1)); // 更新卡车数量
            } else if (t > 0 && (en = map.ceilingEntry(weight - y)) != null) { // 否则，尝试使用拖斗增强
                t--; // 使用一个拖斗
                map.compute(en.getKey(), (k, v) -> (v <= 1 ? null : v - 1)); // 更新卡车数量
            } else {
                return false; // 如果都不满足，返回false
            }
        }
        return true; // 能够运输，返回true
    }
}

ID

Time

1000ms

Memory

256MiB

Difficulty

Tags

二分

# Submissions

Accepted

Uploaded By

TaZi

1 solutions

题面描述

思路：二分答案 + 贪心算法

题解

时间复杂度

代码

Information

Status

Development

Support