https://ac.nowcoder.com/acm/contest/11174

D - 牛客推荐系统开发之动态特征获取

 

题意:每个特征有有时间戳,且保质期都为 yy,在时间戳+ yy 秒后会失效,每个特征都有优先级,越近使用的特征的优先级越高,内存中只能存放优先级最高的 mm 个特征,问 nn 次交互中各次是否需要重新取特征。

双端队列

在内存中需要两个条件:未过期,且优先级在前 mm 个。

因此维护两个双端队列:时间戳队列,队列中的特征都未过期;优先级队列,队列中的特征的优先级都在前 mm

可以直接把按照时间排序后的交互队列作为,优先级队列,只需要记录门槛,保证门槛右侧的都是前 mm。记录每个特征最近被使用的时间,只要判断这个时间是否位于门槛右侧就能判断优先级是否满足条件。

在维护时间戳队列时需要记录每个特征在队列中的次数,因为一个特征可能先由于优先级不够而离开内存,但由于没有过期,所以在时间戳队列中仍然存在,当再次交互时需要重新取,因此又放进了时间戳队列中,导致在时间戳队列中有两个这个特征。

因此仅当一个特征在时间戳队列中出现次数为 0 时才能视为过期。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>

#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 5e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const ll inv2 = (mod + 1) / 2;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;

int n, m, y;
int ans[N];

struct Q {
int id, qid;
ll t;

bool operator<(const Q &b) const {
return t < b.t;
}
} a[N];

unordered_map<int, int> bes, liv;
Q q[N];
int l, r;

int main() {
scanf("%d%d%d", &n, &m, &y);
for (int i = 1; i <= n; i++)scanf("%d%lld", &a[i].id, &a[i].t), a[i].qid = i;
sort(a + 1, a + n + 1);
int k = m;
l = 1, r = 0;
int L = 1;
for (int i = 1; i <= n; i++) {
while (r >= l && a[i].t - q[l].t >= y) {
liv[q[l].id]--;
if (!liv[q[l].id] && bes[q[l].id] >= L)k++;
l++;
}
if (liv[a[i].id] && bes[a[i].id] >= L) {
ans[a[i].qid] = 1;
bes[a[i].id] = i;
} else {
ans[a[i].qid] = 0;
q[++r] = a[i];
liv[a[i].id]++;
bes[a[i].id] = i;
k--;
while (k < 0) {
if (liv[a[L].id] && bes[a[L].id] == L)k++;
L++;
}
}
}
for (int i = 1; i <= n; i++)puts(ans[i] ? "NO" : "YES");
return 0;
}