学步园

1.map

key只能对应一个映射值，支持插入，删除，查找（count, find), 修改（先删除此值，再插入修改后的值），排序，映射（离散话） multimap同样的键值可有多个映射

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <map>

using namespace std;
map<int, int>mp;

int main( )
{
int N,M, t;
char str[1000];
while( scanf("%d%d",&N,&M) != EOF )
  {
    mp.clear( ); 
for( int i = 1; i <= N; i++)
    {
        scanf("%d",&t);
        mp[t]++;
    }
for( int i = 1; i <= M; i++)
    {
       scanf("%s",str);
if( str[0] == 'D' )
        scanf("%d",&t),mp.erase(t);
else if( str[0] == 'F')
       {
         scanf("%d",&t);
if( mp.find(t) != mp.end( ))
             puts("1");
else
             puts("-1");
       }
else if( str[0] == 'P')
       {
          map<int,int>::iterator iter = mp.begin( );
          printf("%d",iter->first);
for( int i = 1; i < iter->second; i++)
              printf(" %d",iter->first);
while( iter++ != mp.end( ))
          {
for( int i = 1; i <= iter->second; i++)
                printf(" %d",iter->first);
          }
          puts("");
       }
    }  
  }
return 0;

}

2.set/multiset

一个集合(set)是一个容器，它其中所包含的元素的值是唯一的。这在收集一个数据的具体值的时候是有用的。集合中的元素按一定的顺序排列，并被作为集合 中的实例。一个集合通过一个链表来组织，在插入操作和删除操作上比向量(vector)快，但查找或添加末尾的元素时会有些慢。具体实现采用了红黑树的平 衡二叉树的数据结构。(百度百科）

multiset所包含的元素值不唯一

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
using namespace std;

multiset<int>p;

int main( )
{
int N,M, t;
char str[1000];
while( scanf("%d%d",&N,&M) != EOF )
  {
    p.clear( ); 
for( int i = 1; i <= N; i++)
    {
        scanf("%d",&t);
        p.insert( t );
    }
for( int i = 1; i <= M; i++)
    {
       scanf("%s",str);
if( str[0] == 'D' )
        scanf("%d",&t),p.erase(t);
else if( str[0] == 'F')
       {
         scanf("%d",&t);
if( p.find(t) != p.end( ))
             puts("1");
else
             puts("-1");
       }
else if( str[0] == 'P')
       {
          multiset<int>::iterator iter = p.begin( );
          printf("%d",*iter);
while( ++iter != p.end( ))
          { 
             printf(" %d",*iter);

          }
          puts("");
       }
    }  
  }
return 0;

}

3.HNOI 2004

set,lower_bound强大应用

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <set>
#include <algorithm>

using namespace std;

#define MOD 1000000
set<int>p;
typedef set<int>::iterator it;

const int inf=~0U>>2;

//const int inf = 0x7f7f7f7f;
/*这样赋值会报错，runtime error, 随便改一个大点或小点也能过。
原因可能是插入的宠物特点值为这个时会把它删除。
*/
int main( )
{  
int N, a, b, c,sum = 0;
  scanf("%d",&N);
  p.insert(inf), p.insert(-inf);
while( N-- )
  {
   scanf("%d%d",&a,&b);
if( p.size() == 2)
       p.insert(b),c = a;
else if( a == c )  
       p.insert(b);
else
   { 
       it x = p.lower_bound(b);
int r = *x - b;
int l = b - *(--x);
if( l <= r )
        sum += l, p.erase(x);
else
        sum += r, p.erase(++x);
if( sum >= MOD )
            sum %= MOD;
   } 
  }
  printf("%d\n", sum);
return 0;
}