Books Queries（ CodeForces - 1066C，模拟 + 元素位置）

一.题目链接：

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;
}