HDU 4268 Alice and Bob（贪心+Multiset的应用）-白红宇

HDU 4268 Alice and Bob（贪心+Multiset的应用）

阅读量：5935 次

发布时间：2019-06-19

本文共 1326 字，大约阅读时间需要 4 分钟。

题意： Alice和Bob有n个长方形，有长度和宽度，一个矩形能够覆盖还有一个矩形的条件的是，本身长度大于等于还有一个矩形，且宽度大于等于还有一个矩形。矩形不可旋转。问你Alice最多能覆盖Bob的几个矩形？

思路：贪心，先依照h将Alice和Bob的矩形排序，对于Alice的每一个矩形。假设Bob的矩形的h小于Alice的h，将Bob的w插入到集合中。

然后，在集合中找到不大于Alice矩形d的最大的Bob的d，那么这样做肯定是最优的。

#include
     
        #include
      
         #include
       
          #include
        
           #include
         
            #include
          
            #include
           
             #include
             #include
             
               #include
              
                #include
               
                #include
                 #include
                 
                  #define eps 1e-6 #define LL long long using namespace std; //const int maxn = 100 + 5;//const int INF = 0x3f3f3f3f;struct Card { int h, d;};Card ca[100010], cb[100010];bool cmp1(Card A, Card B) { return A.h < B.h;}multiset
                  
                    ms;int main() {// freopen("input.txt", "r", stdin); int t; cin >> t; int n; while(t--) { cin >> n; ms.clear(); for(int i = 0; i < n; i++) scanf("%d%d", &ca[i].h, &ca[i].d); for(int i = 0; i < n; i++) scanf("%d%d", &cb[i].h, &cb[i].d); sort(ca, ca+n, cmp1); sort(cb, cb+n, cmp1); int pos = 0, ans = 0; for(int i = 0; i < n; i++) { while(pos < n) { if(ca[i].h >= cb[pos].h) { ms.insert(cb[pos].d); pos++; } else break; } if(ms.empty()) continue; multiset
                   
                    ::iterator it = ms.upper_bound(ca[i].d); if(it != ms.begin()) { ans++; ms.erase(--it); } } cout << ans << endl; } return 0;}

转载于:https://www.cnblogs.com/clnchanpin/p/6925435.html

你可能感兴趣的文章