https://ac.nowcoder.com/acm/contest/11174
D - 牛客推荐系统开发之动态特征获取
题意:每个特征有有时间戳,且保质期都为 y,在时间戳+ y 秒后会失效,每个特征都有优先级,越近使用的特征的优先级越高,内存中只能存放优先级最高的 m 个特征,问 n 次交互中各次是否需要重新取特征。
双端队列
在内存中需要两个条件:未过期,且优先级在前 m 个。
因此维护两个双端队列:时间戳队列,队列中的特征都未过期;优先级队列,队列中的特征的优先级都在前 m。
可以直接把按照时间排序后的交互队列作为,优先级队列,只需要记录门槛,保证门槛右侧的都是前 m。记录每个特征最近被使用的时间,只要判断这个时间是否位于门槛右侧就能判断优先级是否满足条件。
在维护时间戳队列时需要记录每个特征在队列中的次数,因为一个特征可能先由于优先级不够而离开内存,但由于没有过期,所以在时间戳队列中仍然存在,当再次交互时需要重新取,因此又放进了时间戳队列中,导致在时间戳队列中有两个这个特征。
因此仅当一个特征在时间戳队列中出现次数为 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; }
|