【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;
}
           

今天好冷，去吃4.8折的老爺鍋啦^_^