这道题目要求我们模拟一个DNS本地缓存系统
1.缓存容量：缓存最多能存储N条记录。
2.URL请求处理： 每秒处理一个URL请求。 如果请求的URL已经存在于缓存中，直接返回from_cache（输出0）。 如果请求的URL不在缓存中，返回from_internet（输出1），并将该URL加入缓存。
3.TTL管理： 每个URL在缓存中都有一个TTL（Time To Live）值，表示其在缓存中的存活时间。 每秒钟，缓存中所有URL的TTL值减1。当TTL值减为0时，该URL从缓存中移除。 如果加入缓存的新URL没有指定TTL，默认TTL值为5秒。 如果有指定TTL，则使用指定的TTL值。
4.缓存替换策略： 当缓存已满且需要加入新的URL时，移除TTL值最小的URL。 如果有多个URL的TTL值相同，则按照先进先出的原则移除最早加入的URL。
1.239. 滑动窗口最大值 - 优先队列入门
TaZi
SU
@ 8 months ago
#include <bits/stdc++.h>
using namespace std;
const int N = 65536;
struct Node //维护一个URL的信息
{
int edt, stt, id; //edt代表生存周期结束时间，stt代表开始时间
bool operator<(const Node& b) const //为了使用优先队列存储要重载运算符<
{ //优先队列应该要将待删除的数放在队列顶，而优先队列默认为大堆顶，所以要将优先删除的 TTL最小的，即结束时间最小的定为最"大"的值，相等时按先进先出原则，按开始时间排序。
if(edt == b.edt) return stt > b.stt;
return edt > b.edt;
}
};
priority_queue<Node> que; //优先队列定义
int n, x, y;
int q[N]; //询问数组
int ttls[N]; //每个URL的ttl
bool f[N]; //记录当前队列中有没有某个URL
int main()
{
cin >> n >> x;
for(int i = 1 ; i <= x ; i ++) { //输入待处理的YLRL
cin >> q[i];
}
for(int &t:ttls) { //将所有的ttl初始化为5
t = 5;
}
cin >> y;
while(y--) { //循环y次
int url, ttl;
cin >> url >> ttl;
ttls[url] = ttl; //更新这些URL的ttl
}
for(int i = 1 ; i <= x ; i++) {
while(que.size() && que.top().edt <= i) { //删除所有结束时间在i之前的本地缓存
f[que.top().id] = 0;
que.pop();
}
if(f[q[i]]) { //如果本地缓存中有输出0
cout << 0 << " \n"[i==x];
} else {
cout << 1 << " \n"[i==x]; //没有则输出1，然后添加到本地缓存中
if(que.size() == n) { //如果满了删除队列顶一个元素
f[que.top().id] = 0;
que.pop();
}
f[q[i]] = 1;
que.push({i+ttls[q[i]], i, q[i]});//将当前的URL放入队列
}
}
}
import copy
from queue import PriorityQueue
N, X = map(int, input().strip().split()) # 输入 DNS 缓存上限和 TTL 上限
askurls = list(map(int, input().strip().split())) # 多次 DNS 查询的 URL 序列
urltmap = {}
Y = int(input().strip())
for i in range(Y):
url, ttl = map(int, input().strip().split()) # 输入 DNS 地址以及相应的生存周期 TTL
urltmap[url] = ttl # 将 URL 和 TTL 存储在字典 urltmap 中
ans = ""
fn = [False] * 65536 # 初始化布尔数组 fn，用于判断某个 URL 是否已经被缓存
pq = PriorityQueue() # 初始化优先队列 pq，用于维护本地 DNS 缓存
for i in range(len(askurls)):
while not pq.empty() and pq.queue[0][0] <= i:
# 找到优先队列中已过期的生存周期的 URL，进行删除处理
cur = pq.get()
fn[cur[2]] = False
# 如果当前 URL 已经被缓存，则将结果字符串连接 "0 "
if fn[askurls[i]]:
ans += "0 "
else: # 否则当前 URL 还未被缓存，则将结果字符串连接 "1 "
ans += "1 "
if len(pq.queue) >= N: # 如果已缓存的 URL 数量达到 DNS 缓存上限 N，则进行删除处理
cur = pq.get() # 取出优先级最高的 URL，进行删除处理
fn[cur[2]] = False # 将被删除的 URL 对应的缓存状态设置为 False
pq.put((i+urltmap.get(askurls[i], 5), i, askurls[i])) # 将当前 URL 存储在优先队列中，并根据 TTL 计算其生存周期结束时间
fn[askurls[i]] = True # 将当前 URL 对应的缓存状态设置为 True，表示已被缓存
print(ans[:-1]) # 输出结果字符串
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int n= scanner.nextInt(),x= scanner.nextInt();
int[] url=new int[x];
int max=0;
for (int i = 0; i < x; i++) {
url[i]= scanner.nextInt();
}
int y= scanner.nextInt();
Map<Integer,Integer> map=new HashMap<>();
for(int i=0;i<y;i++){
map.put(scanner.nextInt(),scanner.nextInt());
}
PriorityQueue<int[]> pq=new PriorityQueue<>((o1, o2) -> o1[1]==o2[1]?o1[0]-o2[0]:o1[1]-o2[1]);
Map<Integer,int[]> cache=new HashMap<>();
int[] ans=new int[x];
for(int i=0;i<x;i++){
//先删除持续时间结束的
while(pq.size()>0&&pq.peek()[1]<=i){
int[] rem=pq.poll();
cache.remove(rem[2]);
}
if(cache.containsKey(url[i])){
ans[i]=0;
}else {
ans[i]=1;
//如果优先队列的第一个元素的结束时间小于当前时间
if(pq.size()==n){
int[] rem=pq.poll();
cache.remove(rem[2]);
}
//开始时间 结束时间 url
int[] add=new int[]{i,i+map.getOrDefault(url[i],5),url[i]};
pq.offer(add);
cache.put(url[i],add);
}
}
for(int i=0;i<x;i++){
System.out.print(ans[i]+" ");
}
}
}
// by 月与海
package main
import (
"fmt"
)
const N = 70000
var n, x, y, idx int
var urls, tls map[int]int //urls: key url,value ttl
var q, ans, seq []int //seq记录url进入的时机
func getMin() int {
//选择缓存中ttl最小的删除
var res int = -1
minTtl := N
for url, ttl := range urls {
if ttl < minTtl {
minTtl = ttl
res = url
} else if ttl == minTtl {
if seq[url] < seq[res] {
res = url
}
}
}
return res
}
func main() {
//初始化所有slice和map
q = make([]int, N)
ans = make([]int, N)
seq = make([]int, N)
urls, tls = make(map[int]int), make(map[int]int)
fmt.Scan(&n, &x)
for i := 0; i < x; i++ {
fmt.Scan(&q[i])
}
fmt.Scan(&y)
for i := 0; i < y; i++ {
//初始化urls序列
var url, ttl int
fmt.Scan(&url, &ttl)
tls[url] = ttl
}
//每1秒输入一个URL地址 那么x有个暗含的意思就是处理时间
for i := 0; i < x; i++ {
//先从本地DNS上查找，如果本地缓存中能查到就直接返回from_cache -> 0
if _, ok := urls[q[i]]; ok {
ans[i] = 0
} else {
//本地缓存中查不到 -> from_internet 1
ans[i] = 1
//将这条url加入 urls中 先判断有没有装满 如果装满了就ttl最小的移除 如果ttl一样 就将入队时间早的移除
if len(urls) == n {
delete(urls, getMin())
}
//将url 放入urls 从URL的属性列表tls上，读取该URL的TTL 并将URL存入缓存系统中;如果在ts上未能读到该URL的TTL,设置默认TTL为5s;
if _, ok := tls[q[i]]; ok {
urls[q[i]] = tls[q[i]]
} else {
urls[q[i]] = 5
}
seq[q[i]] = idx
idx++
}
//一秒结束了 URL地址的TTL每秒减1，当TTL=0时，将该URL地址从缓存系统中移除;
for url := range urls {
urls[url]--
if urls[url] == 0 {
delete(urls, url)
}
}
}
for i := 0; i < x; i++ {
fmt.Printf("%d", ans[i])
if i != x-1 {
fmt.Printf(" ")
}
}
}
// by xchen
// 设置 stdin 接收输入数据
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
input += data;
return;
});
process.stdin.on('end', () => {
// input 数组以字符串形式存储了所有输入内容。input[i] 存储第i行的所有内容.
input = input.split('\n');
// 获取输入参数
const param0 = input[0].split(' ')
const N = Number(param0[0]) // 缓存容量
const X = Number(param0[1]) // 请求个数
const urlList = new Array() // url 请求列表
const param1 = input[1].split(' ')
for (let m = 0; m < X; m++) {
urlList.push(Number(param1[m]))
}
const Y = Number(input[2])
const tls = new Map()
for (let i = 0; i < Y; i++) {
let tmp = input[3+i].split(' ')
tls.set(Number(tmp[0]), Number(tmp[1]))
}
const cache = new Array() // 缓存
const set = new Set() // 缓存中 url 集合
// 添加 url 到缓存
function add(url){
if(cache.length < N){
cache.push([url, tls.get(url) || 5])
set.add(url)
} else {
if(set.has(url)){
// 当前 url 已经存在于缓存中，不需要进行任何操作
} else {
// 缓存已满，删除缓存中生命周期最短的 url ，并将新的 url 添加到缓存中
cache.sort((a, b) => a[1]-b[1])
set.delete(cache[0][0])
cache.shift()
cache.push([url, tls.get(url) || 5])
set.add(url)
}
}
}
// 更新缓存中 url 的 TTL
function TTL() {
for(let i = 0; i < cache.length; i++){
cache[i][1] -= 1
let urlTTL = cache[i][1]
if(urlTTL === 0){
set.delete(cache[i][0])
cache.splice(i,1)
i--
}
}
}
let result = new Array()
for (let i = 0; i < X; i++) {
// 更新缓存中 url 的 TTL
TTL()
if(set.has(urlList[i])){
// url 存在于缓存中
result.push('0')
}else{
// url 不存在于缓存中，将其添加至缓存中
result.push('1')
add(urlList[i])
}
}
let ans = ''
for(let i = 0; i < result.length - 1; i++){
ans += result[i] + ' '
}
ans += result[result.length-1]
console.log(ans)
})