关于这道题目的另一种贪心做法
查看原帖
关于这道题目的另一种贪心做法
667448
go_deeper楼主2023/11/10 09:33

先叠甲,这不是题解。

我看到贪心做法都是双指针,自己想的是用 multiset 做。
先用田忌的马比赛齐王的马中第一个比这匹马小的马。
然后田忌用相等的马与齐王剩下的马中相等的马平局。
剩下的比赛就是必输了。

这种贪心好想而且好写。

关键代码

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	
	multiset<int>msa,msb;
	
	for(int i=1;i<=n;i++)msa.insert(a[i]),msb.insert(b[i]);
	
	auto it=msa.begin();
	
	while(it!=msa.end())
	{
		auto pos=msb.lower_bound(*it);
		if(pos==msb.begin())
		{
			it=next(it);
		}
		else 
		{
			pos=prev(pos);
			it=msa.erase(it);
			msb.erase(pos);
			ans+=200;
		}
	}
	
	for(auto c:msa)
	{
		auto pos=msb.lower_bound(c);
		if(pos==msb.end()||*pos!=c)continue;
		msb.erase(pos);
	}
	
	ans-=msb.size()*200;
	
	cout<<ans;
}
2023/11/10 09:33
加载中...