题目描述

E - Sorting Queries

思路：

可以也是需要多次排序的， 并且要对数组的开头和结尾进行操纵，那么用数组模拟l,r可实现O(1)

多次排序 肯定不能 无脑 sort

C++ 代码 (76ms)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <unordered_map>

#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 10;
typedef pair <int, int> PII;
multiset <int> mt;
int a[maxn];
int main()
{
    int Q;
    scanf("%d", &Q);
    int l = 1 , r = 1;
    while(Q --)
    {
        int t, x;
        scanf("%d", &t);
        if(t == 1)
        {
            scanf("%d", &x);
            a[r ++] = x;
        }
        else if(t == 2)
        {
            if(!mt.empty())
            printf("%d\n", *mt.begin()), mt.erase(mt.begin());
            else
            printf("%d\n", a[l ++]);
        }
        else
        {
            while(l < r)
            mt.insert(a[l ++]);
            l = r;
        } 
    }
    return 0;
}

vector 模拟首尾添加过程 (360ms)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <unordered_map>

#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
typedef pair <int, int> PII;
vector <int> alls;
multiset <int> mt;
int main()
{
    int Q;
    scanf("%d", &Q);
    while(Q --)
    {
        int x, t;
        scanf("%d", &x);
        if(x == 1)
        {
            scanf("%d", &t);
            alls.push_back(t);
        }
        else if(x == 2)
        {
            if(!mt.empty())
            {
                printf("%d\n", *mt.begin());
                mt.erase(mt.begin());
//              for(auto t : mt)
//              printf("mt %d ", t);
//              printf("\n");
            }
            else
            {
                printf("%d\n", alls[0]), alls.erase(alls.begin());
//              for(auto t : alls)
//              printf("alls: %d ", t);
//              printf("\n");
            }
        }
        else
        {
            for(auto t : alls)
            mt.insert(t);
            alls.clear();
        }
    }
    return 0;
}