一、题面

UVA11020

二、分析

最近脑子有点不好使吧，这题还想了很久。

对于给定的两个值要满足题面中的条件，那么我们可以把这两个值转化到平面中的坐标去理解。

首先，需要考虑的是维护的所有点其实是一个严格有序的，画个图就可以理解了。

此时，在维护的所有点的基础上，如果来了一个点，我们可以先考虑x坐标。

如果这个点x值比所有维护的点中最小的x值还小，那么它必然是有效的，之间加入，再删除后面被这个点控制的点。

如果这个点的y值比在象限中它前面（相对于x)的点的y值要大，那就不需要加入了，因为被它前面这个点控制了。

如果比它前面这个点的y值小，其实就需要加入，因为本身维护的所有点是有序的，那么这个点加入之后必然是有效的，接下来就可以考虑删除被这个点控制的点了。

删除点的话，只需要考虑后面x值比当前点大的点，且y值比当前点大。画个图就好理解了。

实现的话，用有序的且可以重复的multiset，结合lower_bound和upper_bound。

三、AC代码

 #include <bits/stdc++.h>

 using namespace std;

 struct Node

 {

     int l, c;

     bool operator<(const Node &t)const

     {

         return l < t.l || (l ==  t.l && c < t.c);

     }

 };

 int main()

 {

     //freopen("input.txt", "r", stdin);

     int T, N;

     scanf("%d", &T);

     for(int Case = ; Case <= T; Case++)

     {

         if(Case > )    puts("");

         printf("Case #%d:\n", Case);

         multiset<Node> ST;

         Node p;

         scanf("%d", &N);

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

         {

             scanf("%d %d", &p.l, &p.c);

             multiset<Node>::iterator itr = ST.lower_bound(p);

             if(itr == ST.begin() || (--itr)->c > p.c)

             {

                 ST.insert(p);

                 itr = ST.upper_bound(p);

                 while(itr != ST.end() && itr->c >= p.c) ST.erase(itr++);

             }

             printf("%d\n", ST.size());

         }

     }

     return ;

 }

巴特西

UVA_11020 Efficient Solutions 【平衡二叉搜索树set用法】

一、题面

二、分析

三、AC代码

最新文章

热门文章