推荐|【华为OD-E卷 -39 静态代码扫描服务 100分（python、java、c++、js、c）】

【华为OD-E卷 - 静态代码扫描服务 100分（python、java、c++、js、c）】

题目

静态扫描可以快速识别源代码的缺陷，静态扫描的结果以扫描报告作为输出：
1、文件扫描的成本和文件大小相关，如果文件大小为N，则扫描成本为N个金币
2、扫描报告的缓存成本和文件大小无关，每缓存一个报告需要M个金币
3、扫描报告缓存后，后继再碰到该文件则不需要扫描成本，直接获取缓存结果
给出源代码文件标识序列和文件大小序列，求解采用合理的缓存策略，最少需要的金币数

输入描述

第一行为缓存一个报告金币数M，L<= 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

输出：

用例二：

输入：

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

输出：

python解法

解题思路：
输入数据：

m: 额外的可用时间（每个任务额外的时间）。
f: 一个列表，表示每个任务的频率（任务的出现次数）。
s: 一个列表，表示每个任务的大小（任务所需时间）。
核心思路：

首先，我们需要统计每个任务频率的出现次数。
同时，我们还需要记录每个频率任务的大小（时间需求）。如果有多个任务有相同的频率，我们只需要记录一个任务的大小（第一个出现的大小）。
计算任务总时间：

对于每一个任务的频率 k，我们计算它的总时间：
如果任务出现 count[k] 次，且每个任务大小为 size[k]，那么这个任务组的时间为 count[k] * size[k]。
但是，如果任务组的时间超过了 size[k] + m（即原本的大小加上额外的时间），我们会限制任务的时间为 size[k] + m。
返回结果：

最后将每个频率的任务时间加总，得到最终结果。

# 输入数据
m = int(input())  # 可用的额外时间
f = list(map(int, input().split()))  # 每个任务的频率（出现次数）
s = list(map(int, input().split()))  # 每个任务的大小（所需时间）

# 定义核心函数，计算结果
def getResult(m, f, s):
    max_val = max(f)  # 找到最大频率
    count = [0] * (max_val + 1)  # 用于存储每个频率出现的次数
    size = [0] * (max_val + 1)  # 用于存储每个频率对应的大小（所需时间）

    # 遍历任务，统计频率出现次数，并记录每个频率对应的任务大小
    for i in range(len(f)):
        count[f[i]] += 1  # 任务f[i]的频率出现次数加1
        if size[f[i]] == 0:  # 如果该频率还没有任务大小，则记录该任务的大小
            size[f[i]] = s[i]

    ans = 0  # 最终结果

    # 遍历所有频率，计算总时间
    for k in range(max_val + 1):
        if count[k] > 0:  # 如果某个频率的任务存在
            ans += min(count[k] * size[k], size[k] + m)  # 计算任务的总时间

    return ans  # 返回最终结果

# 调用函数并输出结果
print(getResult(m, f, s))

java解法

解题思路
输入数据：

m：表示额外的时间（用于限制任务大小）。
f：任务频率的数组，表示每个任务出现的次数（频率）。
s：任务大小的数组，表示每个任务的所需时间。
核心思路：

统计每个频率出现的次数（count）。
对于每个频率，存储对应的任务大小（size）。我们只需要记录第一次遇到的任务大小，因为频率相同的任务应该具有相同的大小。
计算任务的总时间：

对于每个频率 k：
计算出该频率任务的总扫描时间（scanCost = count[k] * size[k]）。
计算任务的缓存成本（cacheCost = size[k] + m），即任务大小加上额外的时间。
任务的最终时间应该是 scanCost 和 cacheCost 的最小值。
返回结果：

将所有任务的最小时间加起来，得到最终的总时间

import java.util.*;

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

        // 读取额外的时间 m
        int m = Integer.parseInt(sc.nextLine());

        // 读取频率数组 f 和大小数组 s
        Integer[] f = Arrays.stream(sc.nextLine().split(" ")).map(Integer::parseInt).toArray(Integer[]::new);
        Integer[] s = Arrays.stream(sc.nextLine().split(" ")).map(Integer::parseInt).toArray(Integer[]::new);

        // 调用 getResult 函数并输出结果
        System.out.println(getResult(m, f, s));
    }

    public static int getResult(int m, Integer[] f, Integer[] s) {
        // 使用 HashMap 来存储每个频率的任务出现次数
        Map<Integer, Integer> count = new HashMap<>();
        // 使用 HashMap 来存储每个频率对应的任务大小
        Map<Integer, Integer> size = new HashMap<>();

        // 遍历任务，统计每个频率出现的次数并记录任务的大小
        for (int i = 0; i < f.length; i++) {
            // 更新频率出现的次数
            count.put(f[i], count.getOrDefault(f[i], 0) + 1);
            // 只记录每个频率第一次出现的任务大小
            size.putIfAbsent(f[i], s[i]);
        }

        int totalCost = 0;  // 初始化总时间

        // 遍历所有频率
        for (Integer k : count.keySet()) {
            // 计算当前频率任务的扫描时间
            int scanCost = count.get(k) * size.get(k);
            // 计算任务的缓存成本（大小 + 额外时间 m）
            int cacheCost = size.get(k) + m;
            // 最终任务的时间为两者中的最小值
            totalCost += Math.min(scanCost, cacheCost);
        }

        return totalCost;  // 返回计算得到的总时间
    }
}

C++解法

解题思路
输入数据：

costCache：额外的费用（表示任务大小加上缓存的额外时间）。
identifiers：每个任务的标识符（频率数组），即每个任务的标识符，可能有重复，表示任务出现的次数。
sizes：每个任务的大小数组，表示每个任务所需的时间。
核心思路：

使用两个 map（哈希表）：
occurrence：统计每个任务标识符（identifiers[i]）出现的次数。
sizeMap：记录每个标识符对应的任务大小（sizes[i]）。任务大小只记录第一次出现的值，后续相同标识符的任务不需要更新任务大小。
计算最小金币数：

对于每个任务标识符 id，计算该任务的总时间。
如果任务频率为 count(id)，每个任务的大小为 sizeMap[id]，那么任务组的总时间是 count(id) * sizeMap[id]。
然而，任务的实际时间应当是 min(count(id) * sizeMap[id], sizeMap[id] + costCache)，即计算任务的总时间和缓存时间的最小值。
最终，将所有任务的最小时间加起来，得到最小金币数。
返回结果：

输出计算的总金币数。

#include 
#include 
#include 
#include 

using namespace std;

// 解析输入字符串为整数数组
vector<int> splitToInt(const string& input, char delim) {
    vector<int> output;
    string token;
    istringstream stream(input);
    // 按照给定的分隔符拆分字符串，并转换为整数
    while (getline(stream, token, delim)) {
        output.push_back(stoi(token));  // 将每个拆分出的字符串转换为整数并存入数组
    }
    return output;
}

// 计算所需金币
int minCoins(int costCache, const vector<int>& identifiers, const vector<int>& sizes) {
    // 使用map统计每个任务标识符出现的次数
    map<int, int> occurrence;
    // 使用map记录每个标识符对应的任务大小
    map<int, int> sizeMap;

    // 遍历所有任务标识符
    for (int i = 0; i < identifiers.size(); i++) {
        int id = identifiers[i];
        occurrence[id]++;  // 统计任务标识符出现的次数
        if (sizeMap.find(id) == sizeMap.end()) {  // 如果该标识符还没有记录大小
            sizeMap[id] = sizes[i];  // 记录该标识符对应的任务大小
        }
    }

    int totalCoins = 0;  // 总金币数

    // 遍历所有任务标识符的出现次数
    for (const auto& item : occurrence) {
        int id = item.first;  // 任务标识符
        // 计算任务的最小花费，取任务总扫描时间和缓存时间的最小值
        totalCoins += min(item.second * sizeMap[id], sizeMap[id] + costCache);
    }

    return totalCoins;  // 返回计算得到的总金币数
}

// 主函数负责调用逻辑并处理输入
int main() {
    int costCache;
    cin >> costCache;  // 读取额外的缓存时间

    string idStr, sizeStr;
    cin.ignore();  // 跳过多余的空行
    getline(cin, idStr);  // 读取任务标识符序列
    vector<int> identifiers = splitToInt(idStr, ' ');  // 将标识符拆分成整数数组

    getline(cin, sizeStr);  // 读取任务大小序列
    vector<int> sizes = splitToInt(sizeStr, ' ');  // 将大小拆分成整数数组

    // 调用minCoins函数计算最小金币数并输出结果
    cout << minCoins(costCache, identifiers, sizes) << endl;

    return 0;
}

C解法

解题思路

更新中

JS解法

解题思路
输入数据：

cacheSize：额外的缓存费用（可以理解为给任务额外分配的时间或空间）。
files：每个任务的标识符数组，表示任务的不同标识符（可能重复，表示任务的频率）。
scanCosts：每个任务的扫描成本数组，表示任务完成时所需的时间。
核心思路：

对于每个任务标识符，计算其总的扫描成本和缓存成本：
扫描成本是任务出现的次数 count(file) 与该任务的扫描时间 cost(file) 的乘积，即 count(file) * cost(file)。
缓存成本是任务大小 cost(file) 加上额外的时间 cacheSize，即 cost(file) + cacheSize。
对于每个任务标识符，选择这两者中的最小值作为该任务的实际成本。
最终计算所有任务的总成本。
详细步骤：

首先遍历任务标识符数组 files，记录每个标识符出现的次数（fileCount）以及该标识符对应的扫描成本（fileCost）。
然后，对于每个不同的任务标识符，计算该标识符的最小成本，最终累加得到总的最小成本。
返回结果：

输出所有任务的最小总成本

const readline = require("readline");

// 创建输入接口，用于处理标准输入
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

// 用于存储输入的数据
const inputs = [];

// 监听每一行输入
rl.on("line", (line) => {
    // 将输入行存储到 inputs 数组
    inputs.push(line);
    
    // 当所有输入都读取完毕（总共读取 3 行输入）
    if (inputs.length === 3) {
        // 第一行：缓存大小
        const cacheSize = parseInt(inputs[0]);
        // 第二行：任务标识符数组
        const files = inputs[1].split(" ").map(Number);
        // 第三行：任务扫描成本数组
        const scanCosts = inputs[2].split(" ").map(Number);

        // 计算并输出最小成本
        console.log(calculateMinCost(cacheSize, files, scanCosts));
        
        // 清空 inputs 数组，准备下次输入
        inputs.length = 0;
    }
});

// 计算最小成本的函数
function calculateMinCost(cacheSize, files, scanCosts) {
    // 用于存储每个任务标识符出现的次数
    const fileCount = {};
    // 用于存储每个任务标识符对应的扫描成本
    const fileCost = {};

    // 遍历所有任务标识符
    files.forEach((file, index) => {
        // 更新该任务标识符出现的次数
        if (!fileCount[file]) fileCount[file] = 0;
        fileCount[file]++;
        
        // 记录该任务标识符对应的扫描成本（只记录第一次出现的任务）
        if (!fileCost[file]) {
            fileCost[file] = scanCosts[index];
        }
    });

    // 计算所有任务的最小成本，并返回总和
    return Object.keys(fileCount).reduce((total, file) => {
        const count = fileCount[file];  // 任务标识符出现的次数
        const cost = fileCost[file];    // 任务标识符的扫描成本
        
        // 对于每个任务，选择扫描成本和缓存成本的最小值
        return total + Math.min(count * cost, cost + cacheSize);
    }, 0);  // 初始总成本为 0
}

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏