题目描述:
给定n个数 a[0],[1],,,,a[n-1] 每次把前两个取出来 然后大的放前面,小的放后面
有m次询问 每次问第i次操作时取出来的是多少
解题思路: 很容易推出来 当取到最大值a[index]时后面的就是一个循环 所以分两种情况 第一种i<=index,第二种I>index;(循环可能涉及到初始位置怎么设的问题,可以代个起点);
可以用双端队列模拟一遍 求出基础数组 (也可以数组模拟但麻烦)
ac代码:
#include<bits/stdc++.h> using namespace std; const int MAX=100000+10; int main(){ deque<int> que; int n,m; cin>>n>>m; int a[MAX],b[MAX],c[MAX]; int ma=0; for(int i=0;i<n;i++){ int x; scanf("%d",&x); que.push_back(x); ma=max(x,ma); } int h=1; while(que.front()!=ma){ int x=que.front(); que.pop_front(); int y=que.front(); que.pop_front(); b[h]=y; a[h++]=x; if(x>y) x^=y^=x^=y; que.push_front(y),que.push_back(x); } h--; que.pop_front(); int cc=0; while(!que.empty()){ c[cc++]=que.front(); que.pop_front(); } while(m--){ long long x; scanf("%I64d",&x); if(x<=h){ printf("%d %d\n",a[x],b[x]); } else { printf("%d %d\n",ma,c[(x-h-1)%cc]); } } }