2023.09.13-秋招-第一题-塔子哥送快递

TaZi SU @ 8 months ago

题面描述

塔子哥需要在快递公司按时送达快递，为此他要有效利用运输车。每天接收的快递重量加上前一天未送达的快递重量必须在第二天送完。他可以根据运输车的最大承重来决定出车的次数，最终目标是用最少的出车次数完成所有快递的运输。通过模拟每天的快递接收和运输过程，塔子哥可以计算出所需的最小出车次数。

思路:贪心

如果第 $i$ 天正好能够装完货物，那么我们直接当天运走。但是如果当第 $i$ 天有剩余，我们可以尝试将它们留到下一天运走。

这样做的好处是可能可以让本来需要运两趟的变成一趟。

例如:4 2

3 1 1 1

第一天运送一批，剩下的一个留到第二天。

第二天运送一批

第三天的一个留到第四天

第四天运送一批

思路解析

运输车的容量：每辆运输车的最大承重为 k。这意味着每次出车时，塔子哥可以选择运输最多 k 单位的快递。
每日快递处理：对于第 i 天的快递重量 a[i]，需要考虑以下情况：
- 如果当天的快递 a[i] 加上前一天留下的未送达快递（记为 carry）恰好能够被 k 整除，那么塔子哥可以当天直接出车，将所有的快递送出，不留任何剩余。
- 如果当天的快递和前一天的未送达快递总和大于 k，则需要计算出车的次数，将多余的快递留到下一天运输。
- 如果当日快递量加上前一天未送达的快递重量正好为 k，则当日可以完全装车。
余留快递的处理：如果第 i 天在运输后还有剩余的快递（即总重量未满 k），这部分未送达的快递可以被保留到第 i+1 天运输。这是优化的关键，因为通过将未送达的快递留到下一天，可以将本来需要两次运输的情况合并为一次运输，从而减少总的出车次数。

具体实现步骤

以下是实现该思路的详细步骤：

初始化：
- 设置 carry 为 0，表示前一天未送达的快递重量。
- 设置 trips 为 0，用于记录出车的次数。
遍历每一天：
- 对于每一天的快递 a[i]，将其加到 carry 中。
- 计算当前需要运输的总重量（carry）。
- 计算当天需要的出车次数，这可以通过 (carry + k - 1) // k 来实现，这样可以向上取整。
- 更新 carry 为运输后剩余的快递重量（carry % k）。
输出结果：
- 最终输出总的出车次数 trips。

代码

python

# n:货物数量 k:运输量
n , k = map(int, input().split()) 
# arr:货物重量
arr = list(map(int, input().split())) 
# cnt:运输次数
cnt = 0 
# rest:剩余的货物
rest = 0 
for i in range(n):
    # 如果昨天剩余的货物加上当天的货物先装尽量多
    cnt += (arr[i] + rest) // k 
    # 如果余下的货物大于arr[i],代表昨天剩余的货物还需要留一天
    # 这是不能接受的，剩余的货物必须今天运走
    if (arr[i] + rest) % k > arr[i]:
        cnt += 1
        rest = 0
    else:
        rest = (arr[i] + rest) % k
# 如果最后还有剩余的货物，那么需要再运一趟
if rest > 0:
    cnt += 1
print(cnt)

cpp

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 输入 n:货物数量, k:运输量
    int n, k;
    cin >> n >> k;

    // arr:货物重量
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // cnt:运输次数
    int cnt = 0;
    // rest:剩余的货物
    int rest = 0;

    for (int i = 0; i < n; i++) {
        // 如果昨天剩余的货物加上当天的货物先装尽量多
        cnt += (arr[i] + rest) / k;

        // 如果余下的货物大于 arr[i], 代表昨天剩余的货物还需要留一天
        // 这是不能接受的，剩余的货物必须今天运走
        if ((arr[i] + rest) % k > arr[i]) {
            cnt += 1;
            rest = 0;
        } else {
            rest = (arr[i] + rest) % k;
        }
    }

    // 如果最后还有剩余的货物，那么需要再运一趟
    if (rest > 0) {
        cnt += 1;
    }

    cout << cnt << endl; // 输出运输次数
    return 0;
}

java

import java.util.Scanner;

public class Delivery {

    public static void main(String[] args) {
        // 创建Scanner对象用于输入
        Scanner scanner = new Scanner(System.in);
        
        // 输入 n:货物数量, k:运输量
        int n = scanner.nextInt();
        int k = scanner.nextInt();

        // arr:货物重量
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        // cnt:运输次数
        int cnt = 0;
        // rest:剩余的货物
        int rest = 0;

        for (int i = 0; i < n; i++) {
            // 如果昨天剩余的货物加上当天的货物先装尽量多
            cnt += (arr[i] + rest) / k;

            // 如果余下的货物大于 arr[i], 代表昨天剩余的货物还需要留一天
            // 这是不能接受的，剩余的货物必须今天运走
            if ((arr[i] + rest) % k > arr[i]) {
                cnt += 1;
                rest = 0;
            } else {
                rest = (arr[i] + rest) % k;
            }
        }

        // 如果最后还有剩余的货物，那么需要再运一趟
        if (rest > 0) {
            cnt += 1;
        }

        // 输出运输次数
        System.out.println(cnt);
        
        // 关闭Scanner
        scanner.close();
    }
}

ID

Time

1000ms

Memory

256MiB

Difficulty

Tags

贪心

# Submissions

120

Accepted

Uploaded By

TaZi

1 solutions

题面描述

思路:贪心

思路解析

具体实现步骤

代码

python

cpp

java

Information

Status

Development

Support