Codeforces Round #515 (Div. 3)--C. Books Queries

博主链接

题目

题意：

给Q次操作，可以往书架右边边缘加书或者左边边缘加书或者查询一本书里边缘的最短距离

题解：

用两个数组记录一本书是第几本放右边或左边的书，这样就可以保证如果这本书是当时通过放左边进入书架则距离为<mark>min(L + b[id]-1,R - b[id])</mark>，如果通过右边则是 <mark>min(R + a[id]-1, L - a[id])</mark>，可以自己脑补下

代码：

#include<stdio.h>
#include<bits/stdc++.h>
#define met(a) memset(a,0,sizeof(a))
#define fup(i,a,n,b) for(int i=a;i<n;i+=b)
#define fow(j,a,n,b) for(int j=a;j>0;j-=b)
#define ll long long int
const ll LINF=0x3f3f3f3f3f3f3f;
#define MOD(x) (x)%mod
using namespace std;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
int a[maxn],b[maxn];
int main(int argc, char *argv[]) {
	int q,d;
	char ch[10];
	int id,L=0, R=0;
	int cnt = 0;
	scanf("%d", &q);
	while (q--) {
		cin >> ch >> id;
		if (ch[0] == 'L') {
			++cnt;
			a[id] = ++L;
		}
		else if (ch[0] == 'R') {
			++cnt;
			b[id] = ++R;
		}
		else {
			if (a[id] == 0) {
				printf("%d\n", min(L + b[id]-1,R - b[id]));
			}
			else {
				printf("%d\n", min(R + a[id]-1, L - a[id]));
			}
		}
	}

}