联系方式：26914 收集芒果 TLE

Question

此处提供问题陈述：http://www.spoj.com/problems/CMG/

即使执行 100000 次操作，我的解决方案也不会超过 0.2 秒，但 SPOJ 给出 TLE。

SPOJ 使用 g++ 5.1。我是 SunOS - g++ (GCC) 3.4.3 中的运行代码。

下面是我的代码：

    //Collecting Mango Problem
#include <cstring>
#include <stdlib.h>
#include <sstream>
#include <stdio.h>
#include <vector>
#include <set>
using namespace std;
int *max_mango,*IDX;
vector <int> mango_basket;
void Throw();
void Add(int mango);
int Max();
char operation[9],buf[5];
ostringstream buffer1;
multiset<int> mymultiset;
multiset<int>::iterator it;
string s="";
vector <char> buffer2;

void Add(int x){
        mango_basket.push_back(x);
        mymultiset.insert(x);
}

void Throw(){
        it = mymultiset.find(mango_basket.back());
        mango_basket.pop_back();
        mymultiset.erase(it);
}

int Max(){
    it = mymultiset.end();
    --it;
    return *it;
}

int main ()
{
        int T,N,x;
        scanf("%d",&T);
        if (( 1 <= T ) == (T <= 25)){
                for (int i=0;i<T;i++){
                if(i != 0) {buffer1 << "\nCase " << i + 1 << ":";}
                else {buffer1 << "Case " << i + 1 << ":";}
                scanf("%d",&N);
                scanf("%c",operation);
                mango_basket.clear();
                mymultiset.clear();
                if ((1 <= N) == (N <= 100000)){
                for (int j=0;j<N;j++){
                fgets (operation, 9, stdin);
                switch (operation[0])
                {
                        case 'A':
                        {
                                x=atoi(operation + 2);
                                if ((1 <= x) == (x <= 100000)){
                                Add(x);
                                }
                        }
                        break;
                        case 'R':
                        {
                                if (!mango_basket.empty()){
                                Throw();
                        }
                        }
                        break;
                        case 'Q':
                        {
                                if(!mymultiset.empty()){
                                buffer1 << '\n' << Max();
                                }
                                else{
                                buffer1 << "\nEmpty";
                                }
                        }
                        break;
                }
                }}

        fputs(buffer1.str().c_str(), stdout);
        buffer1.str("");
        buffer1.clear();
        }
        }
        return 0;
}

在我的PC上显示的不同操作的时间消耗如下。

$time ./a.out < ADD_MAX

real    0m0.15s
user    0m0.09s
sys     0m0.00s

$time ./a.out < ADD_REMOVE
Case 1:
1
real    0m0.16s
user    0m0.10s
sys     0m0.00s

$time ./a.out < ADD
Case 1:
99999
real    0m0.19s
user    0m0.14s
sys     0m0.00s

$time ./a.out < ADD_MAX_REMOVE

real    0m0.16s
user    0m0.10s
sys     0m0.00s

每个输入文件包含 100,000 个操作。

欢迎任何意见，因为我对进一步优化有点困惑。

Answer 1

我的解决方案需要固定时间进行插入和删除操作 - O(1) 和 O(log n) 时间用于构建排序的容器（以确定最大值）。

然而，SPOJ 要求所有三个操作的数量级均为 1（常数时间）。

联系方式：26914 收集芒果 TLE

SPOJ: 26914 Collecting Mango TLE

c++

ostream

multiset