题目描述

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

1. 文件扫描的成本与文件大小相关，如果文件大小为 N ，则扫描成本为 N 个金币。
2. 扫描报告的缓存成本与文件大小无关，每缓存一个报告需要 M 个金币。
3. 扫描报告缓存后，后续再次扫描相同文件时，不需要重复扫描，只需要使用缓存结果。

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

输入描述

1. 第一行输入一个整数 M （ 1 ≤ M ≤ 100 ），表示缓存一个报告的金币数。
2. 第二行输入一个文件标识序列： ( F1, F2, F3, ..., Fn ) （1 ≤ Fi ≤ 1000 ），表示源代码文件的标识。
3. 第三行输入文件大小序列： ( S1, S2, S3, ..., Sn ) （1 ≤ Si ≤ 10 ），表示对应文件的大小。

输出描述

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

解题思路

1. 策略：

   • 采用贪心的思想，对于每个标识，要么缓存第一个文件，要么不缓存文件。
   • 使用一个哈希表来记录每个文件是否已缓存。
   • 遍历文件标识序列，对于每个文件：
     • 如果该文件已缓存，则只需要支付扫描费用。
     • 如果该文件未缓存，则支付扫描费用并缓存该文件。

复杂度分析

• 假设文件标识序列的长度为 n ，文件大小序列的长度也为 n ，则时间复杂度为 O(n) ，因为我们仅遍历一次文件序列并进行常数时间的操作（查表和更新状态）。

Java

import java.util.HashMap;
import java.util.Scanner;

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

        int M = sc.nextInt();  // 读取缓存费用
        sc.nextLine();  // 清除换行符

        // 读取文件标识序列
        String[] fileIds = sc.nextLine().split(" ");
        // 读取文件大小序列
        String[] fileSizes = sc.nextLine().split(" ");

        // 用来记录每种标识的文件总大小
        HashMap<Integer, Integer> sumSize = new HashMap<>();
        int n = fileSizes.length;

        // 计算每种文件的总大小
        for (int i = 0; i < n; i++) {
            int fileId = Integer.parseInt(fileIds[i]);
            int fileSize = Integer.parseInt(fileSizes[i]);
            sumSize.put(fileId, sumSize.getOrDefault(fileId, 0) + fileSize);
        }

        int ans = 0;  // 最少金币数

        // 遍历文件标识序列
        for (int i = 0; i < n; i++) {
            int fileId = Integer.parseInt(fileIds[i]);
            int fileSize = Integer.parseInt(fileSizes[i]);

            if (sumSize.get(fileId) == 0) continue;  // 如果文件已处理，则跳过

            // 判断是否缓存该文件
            if (sumSize.get(fileId) - fileSize >= M) {
                ans += M + fileSize;  // 可以缓存该文件
                sumSize.put(fileId, 0);  // 该文件处理完
            } else {
                ans += fileSize;  // 不能缓存，只能支付扫描费用
                sumSize.put(fileId, sumSize.get(fileId) - fileSize);  // 文件部分处理完
            }
        }

        // 输出最少金币数
        System.out.println(ans);
    }
}

C++

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>

using namespace std;

int main() {
    int M;
    cin >> M;  // 读取缓存费用
    cin.ignore();  // 清除换行符

    // 读取文件标识序列
    vector<int> f;
    int x;
    while (cin >> x) {
        f.push_back(x);
        if (getchar() != ' ') break;  // 读取直到遇到空格
    }

    // 读取文件大小序列
    vector<int> s;
    while (cin >> x) {
        s.push_back(x);
        if (getchar() != ' ') break;  // 读取直到遇到空格
    }

    // 用来记录每种文件标识的文件总大小
    unordered_map<int, int> sum_size;
    int n = s.size();
    for (int i = 0; i < n; ++i) {
        sum_size[f[i]] += s[i];
    }

    int ans = 0;  // 最少金币数

    // 遍历文件标识序列
    for (int i = 0; i < n; ++i) {
        if (sum_size[f[i]] == 0) continue;  // 已经处理过的文件跳过

        if (sum_size[f[i]] - s[i] >= M) {
            ans += M + s[i];  // 如果可以缓存该文件
            sum_size[f[i]] = 0;  // 文件处理完毕
        } else {
            ans += s[i];  // 不能缓存，只能支付扫描费用
            sum_size[f[i]] -= s[i];  // 文件部分处理完毕
        }
    }

    // 输出最少金币数
    cout << ans << endl;
    return 0;
}

Python

def main():
    M = int(input())  # 读取缓存费用
    file_ids = list(map(int, input().split()))  # 读取文件标识序列
    file_sizes = list(map(int, input().split()))  # 读取文件大小序列

    # 用来记录每种标识的文件总大小
    sum_size = {}
    n = len(file_sizes)

    # 计算每种文件的总大小
    for i in range(n):
        file_id = file_ids[i]
        file_size = file_sizes[i]
        sum_size[file_id] = sum_size.get(file_id, 0) + file_size

    ans = 0  # 最少金币数

    # 遍历文件标识序列
    for i in range(n):
        file_id = file_ids[i]
        file_size = file_sizes[i]

        if sum_size[file_id] == 0:
            continue  # 如果文件已处理，则跳过

        # 判断是否缓存该文件
        if sum_size[file_id] - file_size >= M:
            ans += M + file_size  # 可以缓存该文件
            sum_size[file_id] = 0  # 该文件处理完
        else:
            ans += file_size  # 不能缓存，只能支付扫描费用
            sum_size[file_id] -= file_size  # 文件部分处理完

    print(ans)  # 输出最少金币数

if __name__ == "__main__":
    main()

题目内容

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

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$

样例1

输入

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

输出

7

说明

文件大小相同，扫描成本均为 $1$ 个金币。

缓存任意文件均不合算，因而最少成本为 $7$ 金币。

样例2

输入

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

输出

9