2015 Benelux Algorithm Programming Contest E-Excellent Engineers

题目大意：有n个人，每个人都有三个物品，排名分别为a[ i ]，b[ i ]，b[ i ]，现在要删掉其中的一些人

如果一个人x的三个物品的排名为a[ x ]，b[ x ]，b[ x ]，若存在另一个人y物品排名为a[ y ]，b[ y ]，b[ y ]，

且a[ y ]<a[ x ] && b[ y ]<b[ x ] && c[ y ]<c[ x ]，则删掉x，问你最后剩下多少人。

思路：一开始肯定要按一个物品的排名进行排序，然后就三个人想了半小时没想出来，感觉要用数据

结构，但是不知道怎么写，看来还是对线段树不太了解！！！！

首先，我们按物品a的排名排序，然后我们用b物品的排名建立线段树维护物品c的最小值即可。

 #include<bits/stdc++.h>

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 using namespace std;

 const int N=1e5+;

 const int inf=0x3f3f3f3f;

 int mn[N<<],n;

 struct node

 {

     int a,b,c;

     bool operator <(const node &t)const

     {

         return a<t.a;

     }

 }w[N];

 void updata(int x,int v,int l,int r,int rt)

 {

     if(l==r)

     {

         mn[rt]=min(mn[rt],v);

         return;

     }

     int m=(l+r)>>;

     if(x<=m) updata(x,v,lson);

     else updata(x,v,rson);

     mn[rt]=min(mn[rt<<],mn[rt<<|]);

 }

 int query(int L,int R,int l,int r,int rt)

 {

     if(l>=L && r<=R) return mn[rt];

     int m=(l+r)>>;

     int ans=inf;

     if(L<=m) ans=min(ans,query(L,R,lson));

     if(R>m) ans=min(ans,query(L,R,rson));

     return ans;

 }

 int main()

 {

     int T; cin>>T;

     while(T--)

     {

         cin>>n;

         for(int i=;i<n;i++) scanf("%d%d%d",&w[i].a,&w[i].b,&w[i].c);

         sort(w,w+n);

         memset(mn,inf,sizeof(mn));

         int ans=;

         for(int i=;i<n;i++)

         {

             int g=query(,w[i].b,,n,);

             if(g>w[i].c) ans++;

             updata(w[i].b,w[i].c,,n,);

         }

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

2015 Benelux Algorithm Programming Contest E-Excellent Engineers

最新文章

热门文章