【CCF 201909-4】推荐系统 Apare_xzc

【CCF 201909-4】推荐系统

题面：

~~乍一看好像是线段树…~~

题意：

就是有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;
}