您的位置: 首页  >  文章  >  STL中map取最大最小键值方法（POJ3481）

STL中map取最大最小键值方法（POJ3481）

分类: 文章 • 2025-01-10 10:09:10
首先介绍一下STL中map的架构：

STL中map取最大最小键值方法（POJ3481）

SGI STL map以红黑树为低层级制，每个节点的内容是一个pair。pair的第一个元素被视为键值（key），第二个元素被视为实值（value）。

那么如何用O(1)的时间去取得最小或者最大的key值相对应的<key,value>对（注意不是value，因为map是以key值即键值来构建平衡树的）。

下面呈现一个代码：

[cpp] view plain copy
  1. #include<iostream>  
  2. #include<map>  
  3.   
  4. using namespace std;  
  5.   
  6. int main()  
  7. {  
  8.     map<int,char> m;  
  9.     m[8] = 'a';  
  10.     m[6] = 'b';  
  11.     m[11] = 'c';  
  12.     m[5] = 'd';  
  13.     m[7] = 'e';      
  14.     m[10] = 'f';  
  15.     m[13] = 'g';  
  16.     m[12] = 'h';  
  17.     m[15] = 'i';  
  18.     map<int,char>::const_iterator it = m.begin();  
  19.     while( it!=m.end() )  
  20.     {  
  21.         cout<<it->first<<" "<<it->second<<endl;  
  22.         it++;         
  23.     }  
  24.       
  25.    <strong> it = m.begin();</strong>//相当于获取了平衡树最左下面（most left）的结点的迭代器   
  26.     cout<<"min "<<it->first<<" "<<it->second<<endl;//最小的key值   
  27.       
  28.     <strong>it = m.end();</strong>//相当于获取了平衡树最右下面（most right）的结点的迭代器   
  29.     <strong>it--; </strong>  
  30.     cout<<"max "<<it->first<<" "<<it->second<<endl; //最大的key值   
  31.       
  32.     system("pause");  
  33.     return 0;  
  34. }  

结果：

STL中map取最大最小键值方法（POJ3481）

可见it在遍历的时候是按照key值的升序顺序迭代的，相当于中序遍历了平衡树。从上面代码可以看到如何在O(1)的时间内完成操作。当然如果是想获取value值的最大最小值所对应的键值对，我认为有三种方法：1.将map转存到vector（类型为pair）中，然后将vector调用sort按照value进行排序，然后取得最大最小值，时间复杂度为O(nlogn)；2.遍历map中的value值，取得最大最小值，时间复杂度为O(n)；3.如果条件允许，为什么不把value的值当做map中的key进行存储呢？map会自动的维护平衡树，插入和删除元素平衡树的性质都不会改变。那么就可以在O(1)的时间内获取最大最小值了。


呈上一道题目：http://poj.org/problem?id=3481

这道题TLE了N次，以为是函数调用的问题，最后才发现是因为输入的时候用的cin而不是scanf，估计在大数据量输入的时候会超时吧。


[cpp] view plain copy
  1. #include<iostream>  
  2. #include<map>  
  3. #include<cstring>  
  4. #include<stdio.h>  
  5. #include<cstdlib>  
  6.   
  7. using namespace std;  
  8.   
  9. map<int,int> m;  
  10. map<int,int>::const_iterator it;  
  11.   
  12. inline int serve_highest_pri()  
  13. {  
  14.     if( m.size()==0 )      
  15.         return 0;  
  16.       
  17.     it = m.end();  
  18.     it--;  
  19.       
  20.     int res = it->second;  
  21.     m.erase(it->first);  
  22.     return res;  
  23. }  
  24.   
  25. inline int serve_lowest_pri()  
  26. {  
  27.     if( m.size()==0 )     
  28.         return 0;  
  29.       
  30.     it = m.begin();  
  31.     int res = it->second;   
  32.     m.erase(it->first);  
  33.     return res;  
  34. }  
  35.   
  36. int main()  
  37. {  
  38.     int k,p,n,res;  
  39.     while( scanf("%d",&n) )      
  40.     {  
  41.         if(n==0)              
  42.         {  
  43.             break;                      
  44.         }  
  45.         else if(n==1)  
  46.         {  
  47.             scanf("%d%d",&k,&p);  
  48.             m[p] = k;   
  49.             continue;         
  50.         }  
  51.         else if(n==2)  
  52.         {  
  53.             res = serve_highest_pri();  
  54.             if(res==0)  
  55.             {  
  56.                 cout<<0<<endl;                   
  57.             }  
  58.             else  
  59.             {  
  60.                 cout<<res<<endl;  
  61.             }  
  62.             continue;  
  63.         }  
  64.         else  
  65.         {  
  66.             res = serve_lowest_pri();  
  67.             if(res==0)  
  68.             {  
  69.                 cout<<0<<endl;                   
  70.             }  
  71.             else  
  72.             {  
  73.                 cout<<res<<endl;  
  74.             }  
  75.         }  
  76.     }//while  
  77.       
  78.     system("pause");  
  79.     return 0;  
  80. }   

Run ID User Problem Result Memory Time Language Code Length Submit Time
12378323 niuliguo 3481 Accepted 776K 454MS G++ 1465B 2013-12-14 16:43:41



注明出处：http://blog.****.net/lavorange/article/details/17320951


相关推荐