2016 ACM Amman Collegiate Programming Contest C Bored Judge

2016 ACM Amman Collegiate Programming Contest C Bored Judge

目录

• • 知识点：数据结构
  • 题意
  • 思路
  • 代码

知识点：数据结构

题目链接

题意

获胜者为得分最高的队伍（得分相同取序号最小），每个事件为序号为x的队伍得到p（可为负）分。求第几个事件之后获胜队伍不再改变，全程不变输出0。

一次初始化TLE，一次读不懂题WA……

“the number of the first event after which the winner of the contest didn’t change”
读成了获胜者没有变化后的第一个事件 （难道不是吗），也就是第一次变化的事件……

？？？

思路

常用的数据结构 ：map > mp

需要支持：

1. 修改指定位置
2. 查询最值

线段树可以做，这里用一种数据结构比较方便。
设键为队伍序号，值为队伍分数。
修改指定位置需要访问键，可以用map，同时更新mp。但数据范围小可用数组代替。

当遇到键值互换的时候可以用map > mp，复杂度与未互换前一样。

查询最值则需要访问值，利用mp的自动排序（值有序且键有序），值最大的键最小即为获胜者。
每次比较与上一次获胜者有没有变化即可。

代码

#include
#define ll long long
#define pii pair
using namespace std;
const ll N=1e5+10;
const ll mod=1e9+7;

ll n,q;
ll point[N];//代替mp
map > mp;
//好像用update命名更好
void insert(ll x,ll p)
{
	mp[point[x]].erase(mp[point[x]].lower_bound(x));//删除更新前的键
	if(mp[point[x]].empty()) mp.erase(point[x]);//mp[i]作为set为空时mp[i]还在，删除mp[i]
	point[x]+=p;//修改指定位置
	mp[point[x]].insert(x);//更新键
}

void init()
{
	memset(point,0,sizeof point);
	mp.clear();
	for(ll i=1; i<=n; i++) mp[0].insert(i);//初始化键的值全为0
}

void solve()
{
	scanf("%lld%lld",&n,&q);
	init();
	ll x,p;
	ll ans=0;
	ll winner=1;
	for(ll i=1; i<=q; i++)
	{
		scanf("%lld%lld",&x,&p);
		insert(x,p);
		if(*((mp.rbegin()->second).begin())!=winner)
		//*((mp.rbegin()：最大值->second：对应的所有键).begin()：的第一个键)：迭代器指向的数字
		{
			ans=i;
			winner=*((mp.rbegin()->second).begin());
		}
	}
	printf("%lldn",ans);
}

int main()
{
	ll t;
	scanf("%lld",&t);
	while(t--)
		solve();
	return 0;
}