HDU 4268 Alice and Bob(贪心+multiset) - c++编程基础

TOP

HDU 4268 Alice and Bob(贪心+multiset)

2015-11-21 00:57:02 来源: 作者: 【大中小】浏览:2次

HDU 4268

题意：Alice与Bob在玩卡片游戏，他们每人有n张卡片，若Alice的一张卡片长与宽都不小于Bob的一张卡片，则Bob的卡片就会被盖住，一张卡片只可以使用一次，且不可旋转求Alice最多可以盖住多少张Bob的卡片。

思路：记录两人卡片情况，并按照长度将两人卡片分别降序排序。遍历两人的卡片，将长度小于Alice的卡片长度的Bob卡片的宽度插入multiset中，在multiset中找到小于等于Alice卡片宽度的第一个数，将这个数给消去且答案+1.//贪心法自行发挥即可。

code：

/*
* @author Novicer
* language : C++/C
*/
#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #include
                
                  #include
                 
                   #include
                  
                    #include
                   
                     #include
                    
                      using namespace std; const double eps(1e-8); typedef long long lint; //const int maxn = 2*100000 + 5; multiset
                     
                      Bob; //multiset
                      
                       Alice; struct card{ int x,y; }; bool cmp(card a, card b){ if(a.x != b.x) return a.x < b.x; else return a.y < b.y; } card al[100005],bo[100005]; int n; int main(){ freopen(input.txt,r,stdin); int T; cin >> T; while(T--){ cin >> n; for(int i = 1 ; i <= n ; i++){ scanf(%d%d,&al[i].x,&al[i].y); } for(int i = 1 ; i <= n ; i++){ scanf(%d%d,&bo[i].x,&bo[i].y); } sort(al+1 , al+n+1 , cmp); sort(bo+1 , bo+n+1 , cmp); // cout << al[1].x << al[1].y << endl; Bob.clear(); multiset
                       
                        ::iterator it; int ans = 0; for(int i = 1,j = 1 ; i <= n ; i++){ for( ; j <= n ; j++){ if(al[i].x >= bo[j].x) Bob.insert(bo[j].y); else break; } // cout << Bob.size() << endl; if(Bob.empty()) continue; it = Bob.lower_bound(al[i].y); if(it != Bob.begin()) it--; if(*it <= al[i].y){ ans++; Bob.erase(it); } } cout << ans << endl; } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：hdu 5310 Souvenir （简单题）	下一篇：c++ RTTI

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: