Codeforces Round #569 (Div. 2) C - Valeriy and Deque（规律）-白红宇

Codeforces Round #569 (Div. 2) C - Valeriy and Deque（规律）

阅读量：385 次

发布时间：2019-03-05

本文共 954 字，大约阅读时间需要 3 分钟。

在这里插入图片描述

题意：给定一个初始序列，每次执行一个操作，把序列的最前面的两个数进行比较，把大的放在序列最前面，小的放到最后，给出q个询问，问第m次操作的序列的最前面的两个数是多少？

思路：可以先设初始序列最大值一开始出现的位置为k，一但到了k进行比较的时候永远都是这个最大值放前面，其他的放后面，其实就是个循环，模拟一遍就可以了。

#include
   
    using namespace std;const int maxn=1e5+1;typedef long long ll;vector
    
     
      >v;ll a[maxn],n,m,k,q,maxx=0,num[maxn<<1],b[maxn<<1],cnt=0,cns;int main(){
   	scanf("%d %d",&n,&q);	k=m=n;	for(int i=1;i<=n;++i)	scanf("%lld",&a[i]),num[i]=a[i],maxx=max(maxx,a[i]);	if(q==0) return 0;	v.push_back({
   0,0});	ll first=a[1];	if(a[1]!=maxx){
   			for(int i=2;i<=n;++i)	{
   		v.push_back({
   first,a[i]});		if(first>a[i]) num[++m]=a[i];		else num[++m]=first,first=a[i];			if(first==maxx) {
   		k=i;break;}	}	}	else k=1;	ll t=v.size()-1;	for(int i=k;i<=m;++i) b[++cnt]=num[i];	while(q--)	{
   		scanf("%lld",&cns);		if(cns<=t){
   			printf("%lld %lld\n",v[cns].first,v[cns].second);			continue;		}		cns-=t;		printf("%lld %lld\n",maxx,(cns%(m-k)==0)?b[cnt]:b[(cns%(m-k))+1]);	}}

转载地址：http://zaewz.baihongyu.com/

你可能感兴趣的文章