一.题目链接:

CodeForces-1066C

二.题目大意:

往书架上放书,现有三种操作.

L:把书放在最左侧

R:把书放在最左侧

?:将编号为 id 的书从书架中弹出最少需要多少步

三.分析:

不好想的就是确定元素的位置.

遍历会超时,由于无序 所以无法二分.

这样想:起初书架为空,规定一个点为原点.

              以原点向左右两侧延伸,正方向从左到右.

              往左放一本书,则 --最左值,并更新为这本书的位置.

              往右放一本书,则 ++最右值,并更新为这本书的位置.

              求位置时,只需求 min(a[id] - l, r - a[id]);

详见代码.

四.代码实现:

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-4
#define PI acos(-1.0)
#define ll long long int
using namespace std;

int a[(int)1e5 * 2 + 10];

int main()
{
    int n;
    scanf("%d", &n);
    int l = 1;
    int r = 0;
    for(int i = 0; i < n; ++i)
    {
        getchar();
        char ch;
        int id;
        scanf("%c %d", &ch, &id);
        if(ch == 'L')
            a[id] = --l;
        else if(ch == 'R')
            a[id] = ++r;
        else
            printf("%d\n", min(a[id] - l, r - a[id]));
    }
    return 0;
}