题目描述:
静态扫描快速快速识别源代码的缺陷,静态扫描的结果以扫描报告作为输出:
1、文件扫描的成本和文件大小相关,如果文件大小为N,则扫描成本为N个金币
2、扫描报告的缓存成本和文件大小无关,每缓存一个报告需要M个金币
3、扫描报告缓存后,后继再碰到该文件则不需要扫描成本,直接获取缓存结果
给出源代码文件标识序列和文件大小序列,求解采用合理的缓存策略,最少需要的金币数。
输入描述:
第一行为缓存一个报告金币数M,1<=M<=100
第二行为文件标识序列:F1,F2,F3...Fn, 其中 1<=N<=10000, 1<=Fi<=1000
第三行为文件大小序列:S1,S2,S3...Sn, 其中 1<=N<=10000, 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
说明:
2号文件出现了8次,扫描加缓存成本共计3+5=8,不缓存成本为3*8=24,显然缓存更优。最优最成本为8+1=9
解题思路:
用字典存储数据{ key1=文件号1: [ 扫描成本 , 出现次数 ] , key2=文件号2: [ 扫描成本 , 出现次数 ] ......}
如果扫描成本*出现次数>扫描成本+缓存成本,那么在第一次扫描后就缓存文件;否则就不缓存,全靠扫描,然后这题就没什么难度了
#华为机试,emo了#
m=int(input())
f=list(map(int,input().split()))
s=list(map(int,input().split()))
dict={}
for i,value in enumerate(f):
if dict.get(value) is None:
dict[value]=[s[i]]
dict[value].append(f.count(value))
baogao=list(dict.items())
sum=0
for item in baogao:
n1=item[1][0]
c1=item[1][1]
if (c1-1)*n1 >m:
sum+=n1+m
else:
sum+=n1*c1
print(sum)