可上 欧弟OJ系统 练习华子OD、大厂真题
绿色聊天软件戳 od1441了解算法冲刺训练（备注【CSDN】否则不通过）

相关推荐阅读

• 【华为OD机考】2025C+2025B+2024E+D卷真题【完全原创题解 | 详细考点分类 | 不断更新题目】
• 【华为OD笔试】2025C+2025B+2024E+D卷真题机考套题汇总【真实反馈，不断更新，限时免费】
• 【华为OD笔试】2024E+D卷命题规律解读【分析500+场OD笔试考点总结】
• 【华为OD流程】性格测试选项+注意事项】

题目练习网址：【贪心】2025C-静态代码扫描服务

题目描述与示例

题目描述

静态扫描可以快速识别源代码的缺陷，静态扫描的结果以扫描报告作为输出：

1. 文件扫描的成本和文件大小相关，如果文件大小为N，则扫描成本为N个金币
2. 扫描报告的缓存成本和文件大小无关，每缓存一个报告需要M个金币
3. 扫描报告缓存后，后继再碰到该文件则不需要扫描成本，直接获取缓存结果

给出源代码文件标识序列和文件大小序列，求解采用合理的缓存策略，最少需要的金币数。

输入描述

第一行为缓存一个报告金币数M，1 <= M <= 100

第二行为文件标识序列：F1,F2,F3,…,Fn。

第三行为文件大小序列：S1,S2,S3,…,Sn。

• 1 <= N <= 10000
• 1 <= Fi <= 1000
• 1 <= Si <= 10

输出描述

采用合理的缓存策略，需要的最少金币数

示例一

输入

5
1 2 2 1 2 3 4
1 1 1 1 1 1 1

输出

7

说明

文件大小相同，扫描成本均为1个金币。缓存任意文件均不合算，因而最少成本为7金币。

示例二

输入

5
2 2 2 2 2 5 2 2 2
3 3 3 3 3 1 3 3 3

输出

9

解题思路

出题人又不做人了，题目非常费解，需要结合示例和说明仔细理解。

题意理解

首先我们需要理解金币会花在什么地方。主要是两个方面

1. 遇到某一个大小为N的文件file的时候，如果对它进行扫描，会花费N个金币
2. 遇到一个文件后，我们可以选择对文件进行缓存，花费M个金币

缓存的好处是什么呢？

缓存的好处在于下次再次遇到这个同一个文件file的时候，不需要重新扫描花费金币了，可以直接获得其内容。

因此，对于示例二而言

5
2 2 2 2 2 5 2 2 2
3 3 3 3 3 1 3 3 3

虽然题目没有给出具体的用例说明，但我们也应该得看懂其含义。

大小为3的文件2在例子中多次出现了，我们在第一次扫描的时候花费了3金币，并且进行缓存花费了5金币，之后多次遇到同一个文件2都不需要再额外花费金币来扫描了。

文件5只出现了一次，因此直接扫描花费1金币，不缓存。

一共花费3+5+1 = 9个金币即为答案。

贪心策略

在读懂题意之后，本题的贪心策略其实非常容易想到。

核心的抉择点在于某一个文件在第一次遇到的时候是否要进行缓存。

如果要进行缓存，显然是在第一次遇到的时候就缓存是最划算的，而不是在第二次、第三次遇到的时候才缓存。

由于我们“开了天眼”，知道某一个文件file在后续数组中会出现的次数，我们设为cnt_file。

假设其文件大小（直接扫描所花费的金币数）为N，如果

• 不进行缓存操作，对于这个file所需要花费的金币即为N * cnt_file（扫描cnt_file次，每次花N金币）
• 进行缓存操作，对于这个file所需要花费的金币即为N + M（扫描1次花费N金币，缓存1次花费M金币）

所以，为了使得对这个file的总花费金币更少，我们只需要取上述两个数值之间的较小值即可。

这个过程可以非常方便地使用哈希表来完成。

代码

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频

# 题目：【贪心】2024E/2025C-静态代码扫描服务
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：贪心，哈希表
# 代码看不懂的地方，请直接在群上提问


# 缓存一次花费的金币数
M = int(input())
# 文件标识id构成的数组
file_lst = list(map(int, input().split()))
# 对应文件的花费构成的数组
cost_lst = list(map(int, input().split()))

# 文件全部都扫描花费金币数的哈希表
cost_scan_dic = dict()
# 文件扫描1次+缓存1次花费的金币数哈希表
cost_cache_dic = dict()

# 遍历所有文件
for file, cost in zip(file_lst, cost_lst):
    # 如果文件是第一次出现，则需要进行第一次扫描
    # cost_scan_dic哈希表储存file键，值为cost
    # 同时也考虑如果对file进行缓存，需要的花费
    # cost_cache_dic储存file键，值为cost + M
    if file not in cost_scan_dic:
        cost_scan_dic[file] = cost
        cost_cache_dic[file] = cost + M
    # 如果文件不是第一次出现，则直接更新cost_scan_dic[file]
    # 为多次对file进行扫描所需要花费的金币数
    else:
        cost_scan_dic[file] += cost


ans = 0
# 上述循环结束后，我们要查看每一个file在上述两种抉择中
# 哪一种花费最小，因此遍历每一个文件标识，取较小值更新入ans即可
for file in cost_scan_dic:
    ans += min(cost_scan_dic[file], cost_cache_dic[file])

print(ans)

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 缓存一次花费的金币数
        int M = scanner.nextInt();
        scanner.nextLine(); // 读取换行符

        // 文件标识id构成的数组
        String[] fileStrings = scanner.nextLine().split(" ");
        int[] fileList = Arrays.stream(fileStrings).mapToInt(Integer::parseInt).toArray();

        // 对应文件的花费构成的数组
        String[] costStrings = scanner.nextLine().split(" ");
        int[] costList = Arrays.stream(costStrings).mapToInt(Integer::parseInt).toArray();

        // 文件全部都扫描花费金币数的哈希表
        Map<Integer, Integer> costScanMap = new HashMap<>();
        // 文件扫描1次+缓存1次花费的金币数哈希表
        Map<Integer, Integer> costCacheMap = new HashMap<>();

        // 遍历所有文件
        for (int i = 0; i < fileList.length; i++) {
            int file = fileList[i];
            int cost = costList[i];

            // 如果文件是第一次出现，则初始化扫描和缓存的花费
            if (!costScanMap.containsKey(file)) {
                costScanMap.put(file, cost);
                costCacheMap.put(file, cost + M);
            } else {
                // 如果文件已出现，则累加扫描花费
                costScanMap.put(file, costScanMap.get(file) + cost);
            }
        }

        int ans = 0;
        // 计算每个文件在扫描和缓存两种方式下的最小花费
        for (int file : costScanMap.keySet()) {
            ans += Math.min(costScanMap.get(file), costCacheMap.get(file));
        }

        System.out.println(ans);
    }
}

C++

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 缓存一次花费的金币数
    int M;
    cin >> M;

    // 输入文件标识id构成的数组
    vector<int> fileList;
    int file;
    while (cin >> file) {
        fileList.push_back(file);
        if (cin.peek() == '\n') break;  // 检测换行符，表示文件标识输入结束
    }

    // 对应文件的花费构成的数组
    vector<int> costList(fileList.size());
    for (int &cost : costList) {
        cin >> cost;
    }

    // 文件全部都扫描花费金币数的哈希表
    unordered_map<int, int> costScanMap;
    // 文件扫描1次+缓存1次花费的金币数哈希表
    unordered_map<int, int> costCacheMap;

    // 遍历所有文件
    for (size_t i = 0; i < fileList.size(); i++) {
        int file = fileList[i];
        int cost = costList[i];

        // 如果文件是第一次出现，则初始化扫描和缓存的花费
        if (costScanMap.find(file) == costScanMap.end()) {
            costScanMap[file] = cost;
            costCacheMap[file] = cost + M;
        } else {
            // 如果文件已出现，则累加扫描花费
            costScanMap[file] += cost;
        }
    }

    int ans = 0;
    // 计算每个文件在扫描和缓存两种方式下的最小花费
    for (const auto &pair : costScanMap) {
        int file = pair.first;
        ans += min(costScanMap[file], costCacheMap[file]);
    }

    cout << ans << endl;

    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>

// 定义文件信息结构体，用于存储每个文件的扫描和缓存成本
typedef struct {
    int file_id;      // 文件标识ID
    int scan_cost;    // 文件多次扫描的总花费
    int cache_cost;   // 文件缓存的花费（一次扫描+缓存）
} FileInfo;

// 查找文件信息的函数，如果不存在则创建新条目
FileInfo* find_or_create_file_info(FileInfo* file_infos, int* num_files, int file_id, int M) {
    for (int i = 0; i < *num_files; i++) {
        if (file_infos[i].file_id == file_id) {
            return &file_infos[i];
        }
    }
    // 如果文件ID不存在，则添加新条目
    file_infos[*num_files].file_id = file_id;
    file_infos[*num_files].scan_cost = 0;
    file_infos[*num_files].cache_cost = M;
    (*num_files)++;
    return &file_infos[*num_files - 1];
}

int main() {
    int M;
    scanf("%d", &M); // 读取缓存一次的花费

    int file_list[10000]; // 假设最多有10000个文件标识
    int cost_list[10000]; // 假设最多有10000个成本
    int file_count = 0;

    // 读取文件标识，直到换行结束
    while (scanf("%d", &file_list[file_count]) == 1) {
        if (getchar() == '\n') break; // 检测换行符，表示文件标识输入结束
        file_count++;
    }
    file_count++; // 包括最后一个文件标识

    // 读取每个文件对应的成本
    for (int i = 0; i < file_count; i++) {
        scanf("%d", &cost_list[i]);
    }

    // 初始化文件信息数组
    FileInfo file_infos[10000]; // 假设最多10000个不同文件
    int num_files = 0; // 当前文件信息数量

    // 遍历所有文件，计算扫描和缓存花费
    for (int i = 0; i < file_count; i++) {
        int file_id = file_list[i];
        int cost = cost_list[i];

        // 查找文件信息，如果不存在则创建
        FileInfo* file_info = find_or_create_file_info(file_infos, &num_files, file_id, M);

        // 如果是第一次出现，初始化扫描和缓存花费
        if (file_info->scan_cost == 0 && file_info->cache_cost == M) {
            file_info->scan_cost = cost;
            file_info->cache_cost = cost + M;
        } else {
            // 如果文件已存在，累加扫描花费
            file_info->scan_cost += cost;
        }
    }

    int total_cost = 0;
    // 计算每个文件的最小花费
    for (int i = 0; i < num_files; i++) {
        total_cost += (file_infos[i].scan_cost < file_infos[i].cache_cost)
                      ? file_infos[i].scan_cost
                      : file_infos[i].cache_cost;
    }

    printf("%d\n", total_cost);

    return 0;
}

Node JavaScript

const readline = require("readline");

// 创建输入接口
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

// 读取输入数据
let input = [];
rl.on("line", (line) => {
    input.push(line);
}).on("close", () => {
    // 缓存一次花费的金币数
    const M = parseInt(input[0]);
    
    // 文件标识id构成的数组
    const file_lst = input[1].split(" ").map(Number);
    
    // 对应文件的花费构成的数组
    const cost_lst = input[2].split(" ").map(Number);

    // 文件全部都扫描花费金币数的哈希表
    const cost_scan_dic = {};
    // 文件扫描1次+缓存1次花费的金币数哈希表
    const cost_cache_dic = {};

    // 遍历所有文件
    for (let i = 0; i < file_lst.length; i++) {
        const file = file_lst[i];
        const cost = cost_lst[i];

        if (!(file in cost_scan_dic)) {
            cost_scan_dic[file] = cost;
            cost_cache_dic[file] = cost + M;
        } else {
            cost_scan_dic[file] += cost;
        }
    }

    let ans = 0;
    // 遍历每一个文件标识，取较小值加入总花费ans
    for (const file in cost_scan_dic) {
        ans += Math.min(cost_scan_dic[file], cost_cache_dic[file]);
    }

    console.log(ans);
});

Go

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func main() {
    reader := bufio.NewReader(os.Stdin)

    // 读取缓存一次花费的金币数
    M_str, _ := reader.ReadString('\n')
    M, _ := strconv.Atoi(strings.TrimSpace(M_str))

    // 读取文件标识id构成的数组
    fileStr, _ := reader.ReadString('\n')
    fileStr = strings.TrimSpace(fileStr)
    file_lst := strings.Split(fileStr, " ")

    // 读取对应文件的花费构成的数组
    costStr, _ := reader.ReadString('\n')
    costStr = strings.TrimSpace(costStr)
    cost_lst := strings.Split(costStr, " ")

    // 文件全部都扫描花费金币数的哈希表
    costScanMap := make(map[int]int)
    // 文件扫描1次+缓存1次花费的金币数哈希表
    costCacheMap := make(map[int]int)

    // 遍历所有文件
    for i := 0; i < len(file_lst); i++ {
        file, _ := strconv.Atoi(file_lst[i])
        cost, _ := strconv.Atoi(cost_lst[i])

        // 如果文件是第一次出现
        if _, exists := costScanMap[file]; !exists {
            costScanMap[file] = cost
            costCacheMap[file] = cost + M
        } else {
            // 文件已存在，累加扫描花费
            costScanMap[file] += cost
        }
    }

    // 计算最终答案
    ans := 0
    for file := range costScanMap {
        ans += min(costScanMap[file], costCacheMap[file])
    }

    fmt.Println(ans)
}

// 辅助函数，用于返回两个整数中的较小值
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

时空复杂度

时间复杂度：O(N)。仅需一次循环

空间复杂度：O(N)。两个哈希表所占空间

---

华为OD算法/大厂面试高频题算法练习冲刺训练

• 华子OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务1000+同学成功上岸！

• 课程讲师为全网200w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

• 90+天陪伴式学习，100+直播课时，300+动画图解视频，500+LeetCode经典题，500+华为OD真题/大厂真题，还有简历修改、模拟面试、陪伴小群、资深HR对接将为你解锁

• 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

• 可查看链接OD真题汇总(持续更新)

• 绿色聊天软件戳 od1441或了解更多