阿里钉钉笔试钉钉笔试钉钉秋招 0923

笔试时间：2025年5月4日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

魔法学院的学生需要调配一种强效药剂，以治疗受伤的村民。药剂的配方要求恰好调配出剂量K的药液。学院里有n种不同的魔法成分，每种成分的剂量是固定的，并且每种成分的库存数量有限。学生需要找出最少需要使用多少个成分，才能刚好凑出所需的总剂量K。

每种成分的剂量是不同的，且必须严格递增排列（例如：2ml、3ml、5ml）。每种成分的库存数量有限，使用时不能超过库存。你需要设计一个方案，用最少的成分数量凑出总剂量K。

输入描述

第一行：一个整数n，表示成分的种类数量（1≤n≤100）

第二行：n个整数Bi，表示每种成分的剂量（1≤Bi≤100）

第三行：n个整数Ci，表示每种成分的库存数量（1≤Ci≤100）

第四行：一个整数K，表示需要调配的总剂量（1≤K≤10000）

输出描述

输出一个整数，表示最少需要使用的成分数量。如果无法恰好凑出剂量K，输出-1。

样例输入

3

2 3 5

2 2 1

10

样例输出

3

样例说明

使用2ml（1个）、3ml（1个）、5ml（1个），总剂量为2+3+5=10ml（满足）。总计1+1+1=3个成分数量。
使用2ml（2个）、3ml（2个）、5ml（0个），总剂量为4+6+0=10ml（满足）。总计2+2+0=4个成分数量。
最少的成分数量为3。

参考题解

解题思路：

将多重背包问题转化为01背包问题，使用二进制优化拆分物品数量。dp[j]表示装满容量j所需的最小物品个数。dp[0] = 0（容量0不需要物品），其他初始化为无穷大（inf）。状态转移：对每种物品进行二进制拆分（1, 2, 4...），对每个拆分后的物品（数量为x，价值为w = x * B[i]），状态转移则为dp[j] = min(dp[j], dp[j - w] + x)。

C++：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> B(n);
    for (int i = 0; i < n; i++) {
        cin >> B[i];
    }
    vector<int> C(n);
    for (int i = 0; i < n; i++) {
        cin >> C[i];
    }
    int k;
    cin >> k;
    
    long long inf = 1LL << 60;
    vector<long long> dp(k + 1, inf);
    dp[0] = 0;
    
    for (int i = 0; i < n; i++) {
        int b = B[i], c = C[i];
        int num = 1;
        while (c > 0) {
            int x = min(num, c);
            int w = x * b;
            if (w <= k) {
                for (int j = k; j >= w; j--) {
                    if (dp[j - w] != inf) {
                        dp[j] = min(dp[j], dp[j - w] + x);
                    }
                }
            }
            c -= x;
            num <<= 1;
        }
    }
    
    if (dp[k] == inf) {
        cout << -1 << endl;
    } else {
        cout << dp[k] << endl;
    }
    return 0;
}

Java：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] B = new int[n];
        for (int i = 0; i < n; i++) {
            B[i] = sc.nextInt();
        }
        int[] C = new int[n];
        for (int i = 0; i < n; i++) {
            C[i] = sc.nextInt();
        }
        int k = sc.nextInt();
        
        long inf = Long.MAX_VALUE / 2;
        long[] dp = new long[k + 1];
        Arrays.fill(dp, inf);
        dp[0] = 0;
        
        for (int i = 0; i < n; i++) {
            int b = B[i], c = C[i];
            int num = 1;
            while (c > 0) {
                int x = Math.min(num, c);
                int w = x * b;
                if (w <= k) {
                    for (int j = k; j >= w; j--) {
                        if (dp[j - w] != inf) {
                            dp[j] = Math.min(dp[j], dp[j - w] + x);
                        }
                    }
                }
                c -= x;
                num <<= 1;
            }
        }
        
        if (dp[k] == inf) {
            System.out.println(-1);
        } else {
            System.out.println(dp[k]);
        }
    }
}

Python：

n = int(input())
B = list(map(int, input().split()))
C = list(map(int, input().split()))
k = int(input())

inf = float('inf')
dp = [inf] * (k + 1)
dp[0] = 0

for i in range(n):
    b, c = B[i], C[i]
    num = 1
    while c > 0:
        x = min(num, c)
        w = x * b
        if w <= k:
            for j in range(k, w - 1, -1):
                if dp[j - w] != inf:
                    dp[j] = min(dp[j], dp[j - w] + x)
        c -= x
        num <<= 1

if dp[k] == inf:
    print(-1)
else:
    print(dp[k])

第二题

F国政府正在修建一条新高速公路，用于从其主要武器工厂向前线运输武器，以支持对邻国的军事行动。该高速公路是一条直线，有n个建筑队在不同点上施工。

最近几天，来自邻国的核攻击威胁显著增加。因此，工程办公室决定为建筑队制定疏散计划，以防核攻击发生。目前，有m个避难所位于新建的高速公路附近。该疏散计划必须为每个建筑队分配一个在攻击时应使用的避难所。

每个避难所的入口必须从内部牢固锁住，以防止避难所本身受到损坏。因此，每个避难所必须至少有一个建筑队在攻击时前往该避难所。办公室还需为每个建筑队提供燃料，以便其在攻击时能够驾驶到分配的避难所。所需的燃料量与建筑队位置到分配避难所的距离成正比。为了最小化疏散成本，办公室希望制定一个总燃料消耗最小的计划。

你的任务是帮助他们设计这样的计划。