题解 P4404 【[JSOI2010]缓存交换】

~~可以证明，~~每一次从cache中删除的主存一定是下次访问最晚的，可以用优先队列维护。 首先当然是要离散化。先倒着扫一遍建出链式结构，再正着扫一遍模拟访问过程，具体实现看代码。 ``` #include<cstdio> #include<cctype> #include<cstring> #include<algorithm> #include<queue> using std::pair; using std::priority_queue; typedef pair<int, int> opt; //first表示下一次访问该主存的时间，second表示这块主存离散化后的序号 int Read() { int x = 0; char c = getchar(); while (!isdigit(c)) { c = getchar(); } while (isdigit(c)) { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); } return x; } int next_query[100005], first_query[100005]; //next_query[opt]表示下一个 与opt使用相同主存的 操作 //first_query[mem]表示 下一次对mem的 操作 void Add_opt(int memory, int order)//构建上边两个数组 { next_query[order] = first_query[memory]; first_query[memory] = order; } void Do_opt(int memory)//维护上边first_query数组 { first_query[memory] = next_query[first_query[memory]]; } int memory[100005], number[100005]; bool inCache[100005];//这块主存是否在cache中 int main() { memset(first_query, 0x3f, sizeof(first_query)); int n = Read(), m = Read(); for (int i = 1; i <= n; ++i) { memory[i] = Read(); number[i] = memory[i]; } std::sort(number + 1, number + n + 1); int size = std::unique(number + 1, number + n + 1) - number - 1; //离散化，从后往前建出每块主存的操作顺序 for (int i = n; i >= 1; --i) { Add_opt(memory[i] = std::lower_bound(number + 1, number + size + 1, memory[i]) - number, i); } int ans = 0; //从前往后贪心操作 priority_queue<opt> cache;//这个单词的读音同cash，不读catch for (int i = 1; i <= n; ++i) { if (!inCache[memory[i]]) { ++ans;//miss了一次 if (cache.size() == m)//cache满了 { inCache[cache.top().second] = 0; cache.pop();//移除下次操作最远的主存 } Do_opt(memory[i]);//进行操作 inCache[memory[i]] = 1; cache.push(opt(first_query[memory[i]], memory[i])); } else { Do_opt(memory[i]); ++m; //std::priority_queue不能modify，那就再push一次，同时让大小限制+1 //之前对这块主存的操作的first 一定小于 新push进去的操作的first //所以对贪心没有影响 cache.push(opt(first_query[memory[i]], memory[i])); } } printf("%d", ans); return 0; } ```