hdu5349 (多校联赛) MZL's simple problem - 简单有关问题 :(

hdu5349 (多校联赛) MZL's simple problem --- 简单问题 :(

here

题意：三种操作，遇到1时添加元素到集合，2时删除最小元素，如集合为空则不操作，3时输出最大值，如集合为空则输出0。

正解：

记录元素个数，和最大值。遇到1，更新最大值；遇到2，元素个数减1，如个数为0，则表示无元素，此时最大值为一个自定义的最小值；遇到3，输出最大值，如个数为0，输出0。

误区：根本就不需要去管最小值，对最小值操作对最大值没有关系，所以也就不需要排序操作了。

的确正解就是这么简单，于是就不附代码了。

主要说说我的惨痛经历。我做这道题时确想的太偏了，没有好好思考其本质。什么 优先队列，multiset集合啊，只能说我想多了。最后还是模拟过了，但是模拟的还是很傻很天真。

虽然并不够优化，但是还是学会了不少东西。

数组模拟的 AC代码：

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<stack>
#include<map>
#include<iostream>
#include<set>
using namespace std;
#define LL long long
#define _LL  __int64
#define max1(a,b) (a)>(b)?(a):(b)
#define min1(a,b) (a)<(b)?(a):(b)
#define pi acos(-1.0)
#define eps 1e-8
#define me(a,b) memset(a,b,sizeof(a))
int b[2000018];
int main()
{
    int m;
    scanf("%d",&m);
    int l=1000005;
    int r=1000004;
    while(m--)
    {
        int n;
        scanf("%d",&n);
        if(n==1)
        {
            int a;
            scanf("%d",&a);
            if(a>=b[r])
                b[++r]=a;
            else  if(a<=b[l])
                b[--l]=a;
            else
            {
                for(int i=l; i<=r; i++)
                {
                    if(b[i]<a)
                        b[i-1]=b[i];
                    else
                        {
                            b[i-1]=a;
                            break;
                        }
                }
                l--;
            }
        }
        else if(n==2)
        {
            if(l<=r)
               {
                   b[l]=0;
                   l++;
               }
        }
        else
        {
            if(l<=r)
                printf("%d\n",b[r]);
            else
                printf("0\n");
        }
    }
    return 0;
}

STL muitlset 集合做的超时了，不过还是学到了一些东西——第一次用muitlset 知道了它与set 的一些差别。 1）：可以有重复的元素   2）：删除元素是，如果用 erase（一个数值），会把集合中所有的这个数都删除。必须要用iterator 指针 才能删除某一个元素

附超时代码纪念：

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<stack>
#include<map>
#include<iostream>
#include<set>
using namespace std;
#define LL long long
#define _LL  __int64
#define max1(a,b) (a)>(b)?(a):(b)
#define min1(a,b) (a)<(b)?(a):(b)
#define pi acos(-1.0)
#define eps 1e-8
#define me(a,b) memset(a,b,sizeof(a))
int main()
{
     int m;
      scanf("%d",&m);
      multiset<int> s; //默认从小到大排序。
      multiset<int>::iterator it;
     while(m--)
     {

        int n;
        scanf("%d",&n);
        if(n==1)
        {
            int a;
            scanf("%d",&a);
            s.insert(a);
        }
        else if(n==2)
        {
            if(s.size())
            {
                it=s.begin();
                s.erase(it);
            }
        }
        else
        {
            if(s.size())
            {
           /*这个地方一直想用指针指向s.end()的上一个元素
           于是就用了 it=s.end()-1; 但是错了,最后知道了std::vector::iterator
           迭代器没有对+和-进行重载*/
           it=s.end();
           it--;
            printf("%d\n",*it);
            }
            else
            printf("0\n");
        }
     }
    return 0;
}