fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_set>
  4. #include <algorithm>
  5. #include <map>
  6. #include <list> 
  7.  
  8. using namespace std;
  9.  
  10. // Hàm tính chi phí dựa trên Quy tắc: Miss = |D|+1, Hit = |D| (hoặc N)
  11. long long calculate_cost(bool is_miss, int N, int current_size) {
  12.     if (is_miss) {
  13.         // Miss: 1 (chuyển lên) + |D| (dịch chuyển)
  14.         return (long long)current_size + 1; 
  15.     } else {
  16.         // Hit: |D| (số dụng cụ bị dịch chuyển)
  17.         return (long long)current_size;
  18.     }
  19. }
  20.  
  21. void solve() {
  22.     int N, k; 
  23.     if (!(cin >> N >> k)) return;
  24.  
  25.     vector<int> requests(k);
  26.     for (int i = 0; i < k; ++i) {
  27.         cin >> requests[i];
  28.     }
  29.  
  30.     // 1. Tiền xử lý lần sử dụng tiếp theo (Optimal strategy)
  31.     map<int, vector<int>> next_use_pos;
  32.     for (int i = 0; i < k; ++i) {
  33.         next_use_pos[requests[i]].push_back(i);
  34.     }
  35.     map<int, int> next_occurrence_ptr;
  36.     for(auto const& [tool_id, positions] : next_use_pos) {
  37.         next_occurrence_ptr[tool_id] = 0;
  38.     }
  39.  
  40.     // List và Set cho Cache
  41.     list<int> cache_list; 
  42.     unordered_set<int> cache_set; 
  43.  
  44.     long long total_cost = 0;
  45.  
  46.     for (int i = 0; i < k; ++i) {
  47.         int current_tool = requests[i];
  48.         bool is_miss = (cache_set.find(current_tool) == cache_set.end());
  49.         int current_size = cache_set.size();
  50.  
  51.         // 1. Tính chi phí
  52.         total_cost += calculate_cost(is_miss, N, current_size);
  53.  
  54.         // 2. Cập nhật Cache
  55.         if (!is_miss) {
  56.             // Hit: Dụng cụ vừa dùng được đẩy lên đầu (vị trí 1)
  57.             cache_list.remove(current_tool);
  58.             cache_list.push_front(current_tool);
  59.         } else {
  60.             // Miss
  61.             // 2a. Cache chưa đầy
  62.             if (current_size < N) {
  63.                 // Thêm mới
  64.             }
  65.             // 2b. Cache đã đầy -> Thay thế theo quy tắc Optimal
  66.             else {
  67.                 int tool_to_remove = -1;
  68.                 int max_next_use_index = -1; 
  69.  
  70.                 // Chiến lược Optimal (Belady): Tìm dụng cụ được dùng lại xa nhất
  71.                 for (int tool : cache_set) {
  72.                     int current_ptr = next_occurrence_ptr[tool];
  73.                     int next_use_index = -1; 
  74.  
  75.                     if (current_ptr < next_use_pos[tool].size()) {
  76.                         next_use_index = next_use_pos[tool][current_ptr]; 
  77.                     }
  78.  
  79.                     if (next_use_index == -1) {
  80.                         tool_to_remove = tool;
  81.                         break;
  82.                     }
  83.  
  84.                     if (next_use_index > max_next_use_index) {
  85.                         max_next_use_index = next_use_index;
  86.                         tool_to_remove = tool;
  87.                     }
  88.                 }
  89.  
  90.                 // Thực hiện thay thế
  91.                 if (tool_to_remove != -1) {
  92.                     cache_set.erase(tool_to_remove);
  93.                     cache_list.remove(tool_to_remove);
  94.                 }
  95.             }
  96.  
  97.             // Thêm dụng cụ mới (luôn ở vị trí 1/đầu list)
  98.             cache_set.insert(current_tool);
  99.             cache_list.push_front(current_tool);
  100.         }
  101.  
  102.         // Cập nhật con trỏ lần xuất hiện tiếp theo 
  103.         next_occurrence_ptr[current_tool]++;
  104.     }
  105.  
  106.     cout << total_cost << endl;
  107. }
  108.  
  109. int main() {
  110.     ios_base::sync_with_stdio(false);
  111.     cin.tie(NULL);
  112.  
  113.     solve(); 
  114.  
  115.     return 0;
  116. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
3 12
1 2 3 2 1 4 2 1 1 2 1 3
stdout
copy 
35
https://ideone.com/xz05NO
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!