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

题意:有一个一维的书架,\(L\)表示在最左端放一本书,\(R\)表示在最右端放一本书,\(?\)表示从左数或从右数,最少数多少次才能得到要找的书.
题解:我们开一个稍微大一点的数组,从它的中间开始模拟,\(L\)就--\(l\)放进去,\(R\)就++\(r\)放进去,然后每次更新某一本书的最新位置,因为后放的肯定离最左侧或最右侧最近,然后两端求差弄个最小值就行.

代码:

int q;

char c;

int idx;

int ans;

int mp[2*N],now[2*N];

int main() {

    ios::sync_with_stdio(false);cin.tie(0);

  	cin>>q;

  	int l=N+1,r=N;

  	 for(int i=1;i<=q;++i){

  	 	cin>>c>>idx;

  	 	if(c=='L'){

  	 		mp[--l]=idx;

  	 		now[idx]=l;

  	 	}

  	 	else if(c=='R'){

  	 		mp[++r]=idx;

  	 		now[idx]=r;

  	 	}

  	 	else{

  	 		ans=min(now[idx]-l,r-now[idx]);

  	 		cout<<ans<<endl;

  	    }

  	 }

    return 0;

}

巴特西

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

最新文章

热门文章