记录一下我的折射再折射大模拟
2026-08-03 19:51:36
发布于：浙江
1阅读
0回复
0点赞
题目描述
某个系统会把最近处理过的消息保存在一个“记忆窗口”中。每条消息有三个属性：
编号 id；
当前 token 数 t；
重要性等级 r。
系统还有一个 token 上限 W。设当前仍在窗口中的所有消息 token 总和为 S。
系统需要依次处理 q 个操作。每当加入一条新消息后，如果 S>W，系统会立刻进行维护。
维护过程如下：
如果当前窗口中存在尚未被压缩过的消息，则选择一条消息压缩。
被选择的消息满足：重要性等级 r 最小；若 r 相同，则编号 id 最小。
若这条消息当前 token 数为 x，压缩后变为
⌈
2
x
⌉.
每条消息最多只能被压缩一次。
重复以上压缩过程，直到 S≤W，或者当前窗口中的消息都已经被压缩过。
如果所有当前消息都已经被压缩过，但仍有 S>W，则不断删除最早进入窗口的消息，直到 S≤W。
你需要模拟这个系统，并回答查询。
输入格式
第一行包含两个整数 q,W，分别表示操作数和 token 上限。
接下来 q 行，每行表示一个操作，格式为以下三种之一：
ADD id t r：向窗口末尾加入一条消息，编号为 id，token 数为 t，重要性等级为 r；
ASK id：查询编号为 id 的消息是否仍在窗口中；
STAT：查询当前窗口状态。
保证所有 ADD 操作中出现的 id 两两不同。
输出格式
对于每个 ASK 和 STAT 操作输出一行。
对于 ASK id：
若编号为 id 的消息仍在窗口中，输出它当前的 token 数；
否则输出 −1。
对于 STAT，输出两个整数 cnt,S，其中 cnt 表示当前窗口中的消息数量，S 表示当前窗口中的 token 总和。
猎奇折射再折射又不会超空间又省时间。虽然不必要，这不是满分代码，n,q<=2e5
#include<bits/stdc++.h>
using namespace std;
struct node{
int t,r;
}a[200005];
map<int,int>mp;
int cnt;
int vis[200004];
int mm[200005];
void add(int x){
if(mp.count(x)){
return;
}
mp[x]=++cnt;
mm[cnt]=x;
}
int q;
long long W;
long long sum;
int xiaoxi;
int main(){
cin>>q>>W;
for(int i=1;i<=q;i++){
string op;
cin>>op;
if(op=="ADD"){
int id,t,r;
cin>>id>>t>>r;
add(id);
a[mp[id]].t=t,a[mp[id]].r=r;
sum+=a[mp[id]].t;
xiaoxi++;
int keshan=1;
while(keshan && sum>W){
int mn=1e9,shan=1e9;
keshan=0;
for(int i=cnt-xiaoxi+1;i<=cnt;i++){
if(vis[i])continue;
keshan=1;
mn=min(mn,a[i].r);
}
for(int i=cnt-xiaoxi+1;i<=cnt;i++){
if(vis[i])continue;
if(mn==a[i].r){
shan=min(shan,mm[i]);
}
}
shan=mp[shan];
vis[shan]=1;
int yuanlai=a[shan].t;
a[shan].t=(a[shan].t+1)/2;
int jianshao=yuanlai-a[shan].t;
sum-=jianshao;
}
while(sum>W){
sum-=a[cnt-xiaoxi+1].t;
xiaoxi--;
}
}else if(op == "ASK"){
int id;
cin>>id;
int x=mp.count(id);
if(!x){
cout<<-1<<endl;
continue;
}
int xx=mp[id];
if(xx<cnt-xiaoxi+1){
cout<<-1<<endl;
}else{
cout<<a[xx].t<<endl;
}
}else{
cout<<xiaoxi<<" "<<sum<<endl;
}
}
return 0;
}
这里空空如也
有帮助，赞一个