列表

详情

NC219172. 牛客推荐系统开发之动态特征获取

描述

牛妹有一个微服务，一开始微服务都没有任何的动态特征，取完动态特征之后会存到机器上，如果机器存储了该动态特征就不需要再取，否则就需要进行服务间通信。每一个动态特征都有相同的置信度秒，如果这个动态特征是在时间戳为秒的时候取的，那么这个动态特征在时间戳秒后（包含秒）会被扔掉，需要重新取这个特征。
牛牛给动态特征定义了优先级，如果某个动态特征的最近使用过，那么它的优先级就更高。例如有两个动态特征，一个动态特征A在之前使用过，另一个动态特征B在动态特征A最后一次使用之后都没有使用过，那么动态特征A的优先级就比动态特征B的优先级高。机器只能存放个动态特征，那么优先级前大的动态特征就会被留下，而优先级比第个动态特征优先级小的就会被扔掉。
现在牛妹有一台机器，微服务需要取次动态特征，每一次会告诉你需要取动态特征的ID以及取动态特征的时间戳（单位秒），你需要判断每次取特征需不需要进行服务间通信。

输入描述

第一行输入三个整数、和，分别表示需要取动态特征的次数、这台机器能存放动态特征的个数以及所有动态特征的置信度。（）
接下来行每行两个整数和，分别表示取动态特征的ID以及取动态特征时的时间戳，不保证时间戳按序给出，保证给出的时间戳是两两不相同的。（）

输出描述

对于每一次取动态特征，输出一行字符串。如果需要进行服务间通信则输出YES，否则输出NO。

示例1

输入: 

8 2 5
1 1
2 2
3 6
2 7
1 8
3 9
2 3
1 4

输出: 

YES
YES
YES
YES
YES
YES
NO
NO

说明:

第1秒，取动态特征1，缓存中没有，则需要服务间通信，将动态特征1放入缓存中，缓存充足不需要进行淘汰。
第2秒，取动态特征2，缓存中没有，则需要服务间通信，将动态特征2放入缓存中，缓存充足不需要进行淘汰。
第3秒，取动态特征2，缓存中有，则不需要服务间通信。
第4秒，取动态特征1，缓存中有，则不需要服务间通信。
第6秒，动态特征1因为不被置信而在缓存中被淘汰。
第6秒，取动态特征3，缓存中没有，则需要服务间通信，将动态特征3放入缓存中，缓存充足不需要进行淘汰。
第7秒，动态特征2因为不被置信而在缓存中被淘汰。
第7秒，取动态特征2，缓存中没有，则需要服务间通信，将动态特征2放入缓存中，缓存充足不需要进行淘汰。
第8秒，取动态特征1，缓存中没有，则需要服务间通信，将动态特征1放入缓存中，此时缓存超出2个动态特征，动态特征3因为优先级是最低的而被淘汰。
第9秒，取动态特征3，缓存中没有，则需要服务间通信，将动态特征3放入缓存中，此时缓存超出2个动态特征，动态特征2因为优先级是最低的而被淘汰。

示例2

输入: 

5 2 100
1 1
2 2
1 3
3 4
2 5

输出: 

YES
YES
NO
YES
YES

说明:

第1秒，取动态特征1，缓存中没有，则需要服务间通信，将动态特征1放入缓存中，缓存充足不需要进行淘汰，此时动态特征1的优先级是最高的。
第2秒，取动态特征2，缓存中没有，则需要服务间通信，将动态特征2放入缓存中，缓存充足不需要进行淘汰，此时动态特征2的优先级是最高的。
第3秒，取动态特征1，缓存中有，则不需要进行服务间通信，此时动态特征1的优先级是最高的。
第4秒，取动态特征3，缓存中没有，则需要服务间通信，将动态特征3放入缓存中，此时缓存超出2个动态特征，动态特征2因为优先级是最低的而被淘汰，此时动态特征3的优先级是最高的。
第5秒，取动态特征2，缓存中没有，则需要服务间通信，将动态特征2放入缓存中，此时缓存超出2个动态特征，动态特征1因为优先级是最低的而被淘汰，此时动态特征2的优先级是最高的。

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 139ms, 内存消耗: 8428K, 提交时间: 2021-06-12 02:50:09 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll i,j,k,n,m,t,now[10050000],cur,res[200500],now2[10050000];
struct sb{
	ll id,t,q;
	bool operator<(const sb x)const{return t<x.t;}
}s[200500];
set<sb> st,nmsl;
vector<sb> v;

int main(){
	scanf("%lld%lld%lld",&n,&m,&t);
	for(i=1;i<=n;i++){
		scanf("%lld%lld",&s[i].id,&s[i].t);
		s[i].q=i;
	}
	sort(s+1,s+n+1);
	for(i=1;i<=n;i++){
		cur=s[i].t;
		v.clear();
		for(auto j:nmsl){
			if(j.t+t>cur){break;}
			v.push_back(j);
		}
		for(auto j:v){
			st.erase(s[now[j.id]]);
			nmsl.erase(j);
			now[j.id]=0;
			now2[j.id]=0;
		}
		if(now[s[i].id]){
			res[s[i].q]=1;
			st.erase(s[now[s[i].id]]);
		}
		else{
			now2[s[i].id]=i;
			nmsl.insert(s[i]);
		}
		st.insert(s[i]);
		now[s[i].id]=i;
		while(st.size()>m){
			nmsl.erase(s[now2[(*st.begin()).id]]);
			now2[(*st.begin()).id]=0;
			now[(*st.begin()).id]=0;
			st.erase(st.begin());
		}
	}
	for(i=1;i<=n;i++){
		puts(res[i]?"NO":"YES");
	}
}

上一题

© 2025 nowcoder.com