ProblemA: 第x个数
Time Limit: 1 Memory Limit: 128 MB Submit 8 Solved 5
Description
silchen得到了长度为N的一个全排列(n个数字互不相同,并且都在[1n]),现在dark di出了一个问题,他会对于这个数列进行M次操作,并且在M次操作之后他会询问silchen第x个数字是什么。
操作有2种类型:
1.将下标[lr]中的数字变为一个递增数列。
2.将下标[lr]中的数字变为一个递减数列。
现在silchen向你来求助了。
Input
第一行输入一个整数T,代表数据组数,T小于等于5
每组数据第一行输入2个整数,分别表示nm其中n是数列长度,m是操作数,nm均不大于1000.
第二行输入n个整数,表示一个排列.
接下去m行3个整数,olr,o为0表示第一种操作,o为1表示第二种操作,保证l,r范围为1到n,且l <= r。
最后输入一个整数x表示要求第x个数字 x范围为1到n。
Output
输出一个数字,表示第x个数字的大小。
Sample Input
1
6 3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3
Sample Output
5
HINT
第一次操作后数列变成 1 2 5 6 3 4
第二次操作后数列变成 1 2 6 5 4 3
第三次操作后数列变成 1 2 5 6 4 3
所以第3个数字是5
呃,感觉模拟就好吧,想不出什么好的优化方法。。。
#include<bits/stdc++.h> using namespace std; const int maxn=1001; int n,T,m,o,r,l,x; int a[maxn]; bool cmp(const int a,const int b) { return a>b; } void solve() { if(!o) { sort(a+l,a+r+1); } else { sort(a+l,a+r+1,cmp); } } int main() { scanf("%d",&T); while(T--) { scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } for(int i=0;i!=m;i++) { scanf("%d %d %d",&o,&l,&r); solve(); } scanf("%d",&x); printf("%d\n",a[x]); } return 0; }