欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【CCF 201909-4】推荐系统 Apare_xzc

程序员文章站 2022-04-06 21:02:30
...

【CCF 201909-4】推荐系统


题面:

乍一看好像是线段树…
【CCF 201909-4】推荐系统 Apare_xzc

【CCF 201909-4】推荐系统 Apare_xzc

题意:

就是有m类商品编号从0开始到m-1,然后每种商品最开始有n件,每一类商品的编号不同,他们有各自的评分。然后查询操作要找出所有商品中评分最高的k个,而且每一类不超过k[i]个,更新操作有添加一个商品和删除一个商品


我的思路:

有是插入又是删除又是排序输入的,不如用map模拟一下。定义一个商品结构体,重载小于号,然后模拟。对于删除商品,map可以用erase()但是要知道迭代器或者key的值(type,id,score)。但是操作的输入只给了我们type和id,我们可以哈希一下,把输入的hash(type,id) = score记录到哈希表中,然后O(1)查找。哈希表可以用unordered_map,但是要重载xxx,我们先自己吧(type,id)哈希成long long. 比如type*1E9+id,然后再用unordered_map

对于插入,直接mp[{type,id,score}]++

对于查询,直接for(auto:mp) 然后模拟即可

ps:这个题的题意(OJ判题)应该是输出的时候一类物品一行,然后按分数为第一关键字降序排列,编号为第二关键字升序排列


AC代码

/*
用户名	 试题名称  提交时间	    代码长度	编程语言	评测结果	得分	时间使用	空间使用
<许智超>	 推荐系统  11-24 16:42	1.984KB	C0X	    正确	100	    4.093s	165.8MB
*/
#include <bits/stdc++.h>
using namespace std;
struct Node{
	int score,id,type;
	Node(){}
	Node(int s,int i,int t):score(s),id(i),type(t){}
	bool operator < (const Node& rhs)const{
		if(score!=rhs.score) return score > rhs.score;
		if(type!=rhs.type) return type<rhs.type;
		return id < rhs.id; 
	}
};
bool cmp(const Node& lhs,const Node& rhs)
{
	if(lhs.type!=rhs.type) return lhs.type<rhs.type;
	if(lhs.id!=rhs.id) return lhs.id<rhs.id;
	return lhs.score > rhs.score;
}
int a[52];
vector<Node> V[52];
#define le9 1000000000
map<Node,int>::iterator it; 
int main()
{
//	freopen("in.txt","r",stdin);
//	freopen("myanser.txt","w",stdout);
	int m,n;
	int idd,scoree,typee;
	scanf("%d%d",&m,&n);
	map<Node,int> mp;
	unordered_map<long long,int> getScore;
	for(int i=1;i<=n;++i)
	{
		scanf("%d%d",&idd,&scoree);
		for(int j=0;j<m;++j)
		{
			mp[Node(scoree,idd,j)]++;
			getScore[1ll*j*1e9+idd] = scoree;
		}
	}
	int op,T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&op);
		switch (op)
		{
			case 1:
				scanf("%d%d%d",&typee,&idd,&scoree);
				mp[Node(scoree,idd,typee)]++;
				getScore[1ll*typee*1e9+idd] = scoree;
				break;
				
			case 2:
				scanf("%d%d",&typee,&idd);
				scoree = getScore[1ll*typee*1e9+idd];
				mp.erase(Node(scoree,idd,typee));
				break;
				
			case 3:
				int tot;
				scanf("%d",&tot);
				for(int i=0;i<m;++i) scanf("%d",a+i),V[i].clear();
				
				int cnt = 0;
				for(it=mp.begin();it!=mp.end();++it)
				{
					Node node = it->first;
					typee = node.type;
					if((int)V[typee].size()<a[typee]&&cnt<tot)
						V[typee].push_back(node),cnt++;
					if(cnt==tot) break;
				}
				for(int i=0;i<m;++i)
				{
					int sz = V[i].size(); 
					if(!sz) printf("-1\n");
					else
					{
//						sort(V[i].begin(),V[i].end(),cmp);
						for(int j=0;j<sz;++j)
							printf("%d%c",V[i][j].id,j+1==(int)V[i].size()?'\n':' ');
					}
				}
				break;
		}
	}
	return 0;
}

今天好冷,去吃4.8折的老爷锅啦^_^