如何巧妙的A掉一道紫题

冯·曼施坦因 · 2019-10-14 14:40:31 · 题解

蒻狗的第一篇题解

此题没有必要这么麻烦，用STL+O2一波暴力即可AC；

巨佬董胤然不喜勿喷；

A和S的处理不需要巨佬的数据结构；（毕竟太小了！）

所以我们用一个加强的vector即可实现（logn)的插入和o（1）的查询。（数据太水没有办法），硬模拟即可水过去； 无话可说。。。。。。

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n,ming;
vector<int>a;
int a1;
//priority_queue<int>que;
int erfen(int be,int en) {
    int mid=be+en>>1;
    if(be==en) {
        return be;
    }
    int hj;
    if(a[mid]<a1) {
        hj=erfen(be,mid);
    } else {
        hj=erfen(mid+1,en);
    }
    return hj;
}//考场上蠢了不会用lower_bound;
int main() {
    freopen("unhappy.in","r",stdin);
    freopen("unhappy.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>n>>ming;
    int i;
    int cnt=0;
    char c;
    for(i=1; i<=n; i++) {
        cin>>c>>a1;
        if(c=='I') {
            if(a1>=ming) {
                if(a.size()>0) {
                    if(a1<a[a.size()-1]) {
                        a.push_back(a1);
                    } else {
                        int w=erfen(0,a.size()-1);//二分查找
                        a.insert(a.begin()+w,a1);
                    }
//              q.push(a1);
                }
            else {
                a.push_back(a1);
            }
        }
        } else if(c=='S') {
            for(int j=0; j<a.size(); j++) {
                a[j]-=a1;
                if(a[j]<ming) {
                    a.erase(a.begin()+j);
                    j--;//这地方调了我五分钟；
                    cnt++;
                }
            }
        } else if(c=='A') {
            for(int j=0; j<a.size(); j++) {
                a[j]+=a1;
            }
        } else if(c=='F') {
            if(a1<a.size()+1)
                cout<<a[a1-1]<<endl;
            else
                cout<<-1<<endl;
        }
    }
    cout<<cnt;
    return 0;
}