Lutece 2151 排名

题目链接: https://acm.uestc.edu.cn/problem/pai-ming/description

题目大意:模拟OJ上的Rank

分析:

这道题,因为有排名二字,看似是跟排序有关的题目。

但实际上,由于只关心一号队伍,所以我们可以把其他队伍分为在一号队伍前面的队伍和后面的队伍。

对于在一号队伍前面的队伍,我使用了一个优先队列来存储。

当有一只队伍过题的时候,可以分为两种情况,一号队伍过题和非一号队伍过题。

非一号队伍过题,如果和一号队伍比较大于一号队伍,则加入优先队列。

这就会有一个问题,重复了怎么办,我们只需要用一个数组记录是否在队列中出现过,如果没有,则当前排名+1。

换句话说,优先队列里存储了比一号队伍排名靠前的队伍及队伍的“影子”。

一号队伍过题,如果当前排名已经是rank1了,那么啥事都不用干。

如果不是,首先rank初始化为1,记录是否在队列中的数组也初始化,声明一个新的优先队列。

然后从原来的优先队列一个一个出元素,操作同非一号队伍过题时一样。

最后将两个优先队列交换,这样子又回到了等待过题的状态。

代码:

#include<bits/stdc++.h>
using namespace std;
struct team
{
	int timu, fashi,name;
	team()
	{
		timu = 0; fashi = 0;
	}
	friend bool operator>(const team& a, const team& b)
	{
		if (a.timu > b.timu)
		{
			return true;
		}
		else if(a.timu == b.timu)
		{
			return a.fashi < b.fashi;
		}
		else if (a.timu < b.timu)
		{
			return false;
		}
		return false;
	}
	friend bool operator<(const team& a,const team& b)
	{
		if (a.timu < b.timu)
		{
			return true;
		}
		else if (a.timu == b.timu)
		{
			return a.fashi > b.fashi;
		}
		else if (a.timu > b.timu)
		{
			return false;
		}
		return false;
	}
	friend bool operator==(const team& a, const team& b)
	{
		return ( a.timu==b.timu ) && (a.fashi == b.fashi);
	}
	team operator=(const team& a)
	{
		this->timu = a.timu;
		this->fashi = a.fashi;
		this->name = a.name;
		return *this;
	}
	void add(int fashivalue)
	{
		this->timu++;
		this->fashi += fashivalue;
	}
};
team teams[100001];
int isqueue[100001];
int main()
{
	ios::sync_with_stdio(false);
	int n, m,t,p,nowrank=1;
	priority_queue<team> pe;
	cin >> n >> m;
	for (int i = 0; i <= n; ++i)
	{
		teams[i].name = i;
	}
	for (int i = 0; i < m; ++i)
	{
		cin >> t >> p;
		if (t == 1)
		{
			if (nowrank == 1)
			{
				teams[1].add(p);
			}
			else
			{
				team linshiteam;
				priority_queue<team> pe2;
				teams[1].add(p);
				nowrank = 1;
				int pesum = pe.size();
				fill(isqueue,isqueue+n+1,0);
				while (pesum--)
				{
					linshiteam = pe.top();
					if (linshiteam > teams[1])
					{
						pe2.push(linshiteam);
						pe.pop();
						if (isqueue[linshiteam.name] == 0)
						{
							++nowrank;
							++isqueue[linshiteam.name];
						}
					}
					else
					{
						break;
					}
				}
				pe.swap(pe2);
			}
		}
		else
		{
			teams[t].add(p);
			if (teams[t] > teams[1])
			{
				pe.push(teams[t]);
				if (isqueue[t] == 0)
				{
					++nowrank;
					++isqueue[t];
				}
			}
		}
		cout << nowrank << endl;
	}
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注