寒假集训4 I.匹配星星(multiset+贪心)
程序员文章站
2022-06-28 21:46:38
...
题目链接:https://ac.nowcoder.com/acm/contest/3005/I
感觉这一题并不难,但过的人不多(我连看都没看呜呜呜)
发现到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;
}
上一篇: 四川去哪里看油菜花 7个最佳赏油菜花景点
下一篇: 筷子有点发霉了怎么办