C++刷题篇——05静态扫描

一、题目

二、解题思路

注意：注意理解题目，缓存的前提是先扫描一次

1、使用两个map，两个map的key相同，map1：key为文件标识，value为文件出现的次数；map2：key为文件标识，value为扫描成本

2、使用循环，求每一类文件的两种方式最优解：

min（文件出现的次数 * 文件标识在file_cost中对应的value即扫描成本， 文件标识在file_cost中对应的value即扫描成本 + 缓存价格）

三、代码

#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<algorithm>using namespace std;vector<int>split(string params) {vector<int>p;while (params.find(" ") != string::npos) {int found = params.find(" ");p.push_back(stoi(params.substr(0, found)));params = params.substr(found + 1);}p.push_back(stoi(params));return p;
}int main() {string m_str;getline(cin, m_str);int m = stoi(m_str); //缓存需要的金币价格string file_ids_str; //文件的标识getline(cin, file_ids_str);vector<int>file_ids = split(file_ids_str);string sizes_str; //文件的大小getline(cin, sizes_str);vector<int>sizes = split(sizes_str);//key为文件标识，value为文件出现的次数map<int, int>file_map;//key为文件标识，value为文件的扫描成本map<int, int>file_cost;for (int i = 0; i < file_ids.size(); i++) {if (file_map.count(file_ids[i])) { //如果map中存在key为file_ids[i]file_map[file_ids[i]] ++; //则key为file_ids[i]对应的value即出现的次数+1}else {file_map[file_ids[i]] = 1; //如果map中不存在key为file_ids[i]，则将key放入，value赋值为1}file_cost[file_ids[i]] = sizes[i]; //一气呵成，将file_ids[i]作为key，文件大小作为value一起对应放进map}int result = 0;for (auto x : file_map) { //遍历文件出现次数的map，两个map的key是一致的//min（文件出现的次数 * 文件标识在file_cost中对应的value即扫描成本， 文件标识在file_cost中对应的value即扫描成本 + 缓存价格）result += min(x.second * file_cost[x.first], file_cost[x.first] + m);}cout << result << endl;return 0;
}