2021 ICPC 江西省大学生程序设计竞赛 J.LRU 二分

题目大意：(吐槽计算机组成原理)计算机内存分块构成，由 1 − n 1-n 1−n编号。现在要求求缓存的块数，使得对于给定的长度为 n n n的请求序列，少 k k k次命中缓存。其中，在命中缓存时有三种情况：

1. 缓存中存在当前请求编号的块，此时命中该编号的缓存；
2. 未命中缓存，缓存未满，当前块写入缓存；
3. 未命中缓存，缓存已满，替换缓存中时间最久的块；

思路：二分一个长度并进行检验，检验时用一个 s e t set set维护 C a c h e Cache Cache中的块编号，并按照请求序列的先后顺序进行排序，用一个 m a p map map维护映射元素上一次的出现位置。

1. 对于命中缓存的情况，先擦除上次的数据，再保存本次的编号；
2. 对于缓存已满的情况，则擦除 s e t set set中的第一个元素(历史最久远的块)，然后插入新块；
3. 缓存未满，直接插入新块。

有一个技巧，在插入元素时不要使用 i n s e r t insert insert，而是使用 e m p l a c e emplace emplace方法，避免插入时多余的一次构造和析构，可以提升程序效率。

#include 
#define int long long
using namespace std;

const int N = 1e5 + 10;
int a[N];

struct node {
    int idx, val;
    bool operator n >> k;
    for(int i = 1; i > a[i];
    int l = 1, r = n + 1, ans = -1;
    while(l > 1;
        if(check(mid, n, k)) r = mid - 1, ans = mid;
        else l = mid + 1;
    }
    if(ans