題目描述
靜態掃描可以快速識別源代碼的缺陷，靜態掃描的結果以掃描報告作為輸出：
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 |
| 輸出 | 7 |
| 說明 | 文件大小相同，掃描成本均為1個金幣。緩存任意文件均不合算，因而最少成本為7金幣。 |
| 輸入 | 5 2 2 2 2 2 5 2 2 2 3 3 3 3 3 1 3 3 3 |
| 輸出 | 9 |
| 說明 | 無 |
靜態掃描成本優化：緩存策略的貪心解法
核心解題思路
題目要求通過合理的緩存策略最小化靜態掃描的總成本，核心問題是：對于重復出現的文件，何時緩存報告最劃算？ 關鍵在于權衡掃描成本與緩存成本：
- 掃描成本：每次掃描文件需支付其大小的金幣（文件越大成本越高）
- 緩存成本：緩存報告需固定支付M金幣（后續相同文件可免掃描）
- 決策關鍵：對每個文件標識，判斷"緩存并復用"還是"每次重新掃描"更經濟
貪心策略
對每個文件標識獨立決策：
- 若不緩存：總成本 = 文件大小 × 出現次數
- 若緩存：總成本 = 第一次掃描成本 + 緩存成本
- 選擇成本更低的方案：
min(文件大小×頻次, 文件大小 + M)
為什么貪心有效？每個文件的緩存決策相互獨立，緩存一個文件不會影響其他文件的掃描成本。
解題步驟詳解
1. 輸入處理與參數設置
# 讀取緩存成本M
M = int(input().strip())# 讀取文件標識序列
file_ids = list(map(int, input().split()))# 讀取文件大小序列
file_sizes = list(map(int, input().split()))
2. 構建文件分組統計
from collections import defaultdict# 創建分組字典：記錄每個標識的[頻次, 總大小, 首次大小]
file_groups = defaultdict(lambda: [0, 0, None])# 遍歷所有文件
for fid, size in zip(file_ids, file_sizes):# 更新出現頻次file_groups[fid][0] += 1# 累加總大小（用于不緩存方案）file_groups[fid][1] += size# 記錄首次出現的大小（用于緩存方案）if file_groups[fid][2] is None:file_groups[fid][2] = size
3. 計算最小成本
total_cost = 0
for fid, (count, total_size, first_size) in file_groups.items():# 不緩存方案：每次掃描cost_no_cache = total_size# 緩存方案：首次掃描+緩存cost_cache = first_size + M# 選擇更經濟的方案total_cost += min(cost_no_cache, cost_cache)
4. 輸出結果
print(total_cost)
關鍵邏輯解析
1. 分組統計的重要性
- 頻次(count)：決定重復掃描的成本
- 總大小(total_size)：計算不緩存方案的總成本
- 首次大小(first_size)：緩存方案只需首次掃描成本
為何記錄首次大小而非任意大小？
緩存發生在首次掃描時，后續文件無論大小如何都復用結果
2. 成本比較的數學原理
決策依據的數學表達式：
min( Σs? , s? + M )
其中：
Σs?：所有出現位置的大小之和s?：首次出現的大小M：固定緩存成本
3. 獨立決策的正確性
- 文件標識相互獨立，緩存決策無耦合
- 緩存文件A不影響文件B的掃描
- 局部最優解之和等于全局最優解
完整代碼實現
from collections import defaultdictdef main():# 讀取緩存成本M = int(input().strip())# 讀取文件標識序列file_ids = list(map(int, input().split()))# 讀取文件大小序列file_sizes = list(map(int, input().split()))# 創建分組統計字典# 格式: {文件標識: [出現次數, 總大小, 首次大小]}file_groups = defaultdict(lambda: [0, 0, None])# 遍歷所有文件for fid, size in zip(file_ids, file_sizes):# 更新出現次數file_groups[fid][0] += 1# 累加總大小file_groups[fid][1] += size# 記錄首次大小if file_groups[fid][2] is None:file_groups[fid][2] = size# 計算最小總成本total_cost = 0for fid, (count, total_size, first_size) in file_groups.items():# 計算兩種方案成本cost_no_cache = total_sizecost_cache = first_size + M# 選擇更經濟的方案total_cost += min(cost_no_cache, cost_cache)print(total_cost)if __name__ == "__main__":main()
復雜度分析
- 時間復雜度：O(N)
- 遍歷文件序列：O(N)
- 分組統計：O(N)
- 決策計算：O(K)（K為唯一文件數，K ≤ N）
- 空間復雜度：O(K)
- 存儲分組信息：O(K)（K為唯一文件標識數）
示例驗證
示例1：
輸入：
5
1 2 2 1 2 3 4
1 1 1 1 1 1 1
處理流程：
- 分組統計：
- 文件1: [頻次=2, 總大小=2, 首次大小=1]
- 文件2: [頻次=3, 總大小=3, 首次大小=1]
- 文件3: [頻次=1, 總大小=1, 首次大小=1]
- 文件4: [頻次=1, 總大小=1, 首次大小=1]
- 成本決策：
- 文件1: min(2, 1+5)=2
- 文件2: min(3, 1+5)=3
- 文件3: min(1, 1+5)=1
- 文件4: min(1, 1+5)=1
- 總成本：2+3+1+1=7
輸出：7
示例2：
輸入：
5
2 2 2 2 2 5 2 2 2
3 3 3 3 3 1 3 3 3
處理流程：
- 分組統計：
- 文件2: [頻次=8, 總大小=24, 首次大小=3]
- 文件5: [頻次=1, 總大小=1, 首次大小=1]
- 成本決策：
- 文件2: min(24, 3+5)=8
- 文件5: min(1, 1+5)=1
- 總成本：8+1=9
輸出：9
總結
通過貪心策略解決靜態掃描成本優化問題：
- 問題特性：重復文件可復用緩存，決策相互獨立
- 核心洞察：緩存的價值 = 后續掃描成本節省 - 緩存成本
- 算法選擇：分組統計 + 成本比較（O(N)時間復雜度）
- 優化關鍵：
- 小文件高頻：傾向不緩存（如示例1）
- 大文件高頻：傾向緩存（如示例2）
- 低頻文件：通常不緩存
實際應用場景：編譯器構建系統（如Makefile）、CI/CD流水線，通過緩存中間結果加速重復構建過程。
