fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_set>
  4. #include <algorithm>
  5. #include <limits>
  6.  
  7. using namespace std;
  8.  
  9. // Hàm tìm chỉ mục của lần sử dụng tiếp theo của một dụng cụ
  10. // Bắt đầu tìm từ vị trí 'start_index'
  11. // Trả về -1 nếu dụng cụ đó không được sử dụng lại nữa
  12. int find_next_use(int tool_id, int start_index, const vector<int>& requests) {
  13.     for (int j = start_index; j < requests.size(); ++j) {
  14.         if (requests[j] == tool_id) {
  15.             return j;
  16.         }
  17.     }
  18.     return -1; // Không bao giờ được dùng lại
  19. }
  20.  
  21. void solve() {
  22.     // N: Kích thước cache (theo đề bài: N <= 1000)
  23.     // k: Độ dài chuỗi yêu cầu (theo đề bài: k <= 20000)
  24.     int N, k;
  25.     if (!(cin >> N >> k)) return;
  26.  
  27.     // requests: Chuỗi yêu cầu dụng cụ a1, a2, ..., ak
  28.     vector<int> requests(k);
  29.     for (int i = 0; i < k; ++i) {
  30.         cin >> requests[i];
  31.     }
  32.  
  33.     // cache: Tập hợp các dụng cụ hiện có trong cache
  34.     unordered_set<int> cache;
  35.     int miss_count = 0;
  36.  
  37.     // Duyệt qua chuỗi yêu cầu
  38.     for (int i = 0; i < k; ++i) {
  39.         int current_tool = requests[i];
  40.  
  41.         // 1. Cache Hit (Dụng cụ có sẵn)
  42.         if (cache.count(current_tool)) {
  43.             continue;
  44.         }
  45.  
  46.         // 2. Cache Miss (Dụng cụ chưa có)
  47.         miss_count++;
  48.  
  49.         // 2a. Cache chưa đầy
  50.         if (cache.size() < N) {
  51.             cache.insert(current_tool);
  52.         }
  53.         // 2b. Cache đã đầy -> Phải thay thế
  54.         else {
  55.             int tool_to_remove = -1;
  56.             // Chỉ số xa nhất của lần sử dụng tiếp theo
  57.             int max_next_use = -1; // -1 đại diện cho việc không bao giờ dùng lại
  58.  
  59.             // Thuật toán Tham lam Tối ưu:
  60.             // Chọn dụng cụ trong cache có lần sử dụng tiếp theo xa nhất (max_next_use lớn nhất)
  61.             for (int tool : cache) {
  62.                 // Tìm lần sử dụng tiếp theo, bắt đầu từ vị trí i+1
  63.                 int next_use = find_next_use(tool, i + 1, requests);
  64.  
  65.                 // Nếu dụng cụ không bao giờ được dùng lại (next_use == -1), 
  66.                 // thì nó là ứng viên tốt nhất để loại bỏ.
  67.                 if (next_use == -1) {
  68.                     tool_to_remove = tool;
  69.                     break; // Ưu tiên tuyệt đối, dừng tìm kiếm
  70.                 }
  71.  
  72.                 // So sánh chỉ số lần dùng tiếp theo
  73.                 if (next_use > max_next_use) {
  74.                     max_next_use = next_use;
  75.                     tool_to_remove = tool;
  76.                 }
  77.             }
  78.  
  79.             // Thực hiện thay thế
  80.             if (tool_to_remove != -1) {
  81.                 cache.erase(tool_to_remove);
  82.             }
  83.             cache.insert(current_tool);
  84.         }
  85.     }
  86.  
  87.     // Kết quả là số lần thao tác (số lần Cache Miss)
  88.     cout << miss_count << endl;
  89. }
  90.  
  91. int main() {
  92.     // Tối ưu hóa I/O
  93.     ios_base::sync_with_stdio(false);
  94.     cin.tie(NULL);
  95.  
  96.     solve();
  97.  
  98.     return 0;
  99. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
3 12
1 2 3 2 1 4 2 1 1 2 1 3
stdout
copy 
5
https://ideone.com/nMSXZ2
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!