欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

寒假集训4 I.匹配星星(multiset+贪心)

程序员文章站 2022-06-28 21:46:38
...

题目链接:https://ac.nowcoder.com/acm/contest/3005/I
寒假集训4 I.匹配星星(multiset+贪心)寒假集训4 I.匹配星星(multiset+贪心)感觉这一题并不难,但过的人不多(我连看都没看呜呜呜)
发现到z只会为0和1,这一题就好做了
先对x进行一波排序,然后因为z只有两种情况0和1,对z进行讨论,如果z=0则让它进行multiset中;如果z=1,那么就在当前multiset中进行查找比它的y小的最大的y进行匹配(因为后面即使还有z=0的点j,因为xi<xj,也无法与j进行匹配)。
AC代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
struct node
{
	int a;int b;int c;
}star[110000];
bool cmp(node x,node y)
{
	return x.a==y.a?(x.c<y.c):(x.a<y.a);  
	//这里写成这样也可以
	//return x.a==y.a?(x.b<y.b):(x.a<y.a);
}
int main()
{
	int n;
	cin>>n;
	int ans=0;
	for(int i=0;i<n;i++)
		scanf("%d%d%d",&star[i].a,&star[i].b,&star[i].c);
	sort(star,star+n,cmp);
	multiset<int> m;
	for(int i=0;i<n;i++)
	{
		if(star[i].c)
		{
			auto t=m.lower_bound(star[i].b);
			if(t!=m.begin())
			{
				t--;
				m.erase(t);
				ans+=1;
			}
		}
		else
			m.insert(star[i].b);
	}
	cout<<ans<<endl;
	return 0;
}