发布时间: 2017年7月9日 20:20 最后更新: 2017年7月10日 21:11 时间限制: 1000ms 内存限制: 128M
描述给定一个长度为 n 的非负整数序列，下标为 0 , 1 ,…, n−1 .
定义： sequence(K) ： 由下标为 K 的倍数组成的子序列,即下标为 0 , K , 2K ,..., [n−1/k]∗k
query(K,S) : 询问 sequence(K) 中的第 S 大的数字
输入第一行一个整数 T ，表示测试组数。 对于每组数据，第一行输入两个整数 n , m ， 1<=n<=20000 , 1<=m<=100000 ， n 表示序列的长度， m 表示询问个数。 接下来一行是 n 个整数 a0,a1,..,an−1,0<=ai<231 , i=0,1,…,n−1 ，表示序列。 接下来 m 行，每行两个整数 K,S 0 < K <= 109 , 1<=S<=n
输出每组数据对于每个询问输出一行，若 sequence(K) 的元素个数小于 S ，输出 −1 ；否则输出 query(K,S)
样例输入1 复制 1 5 2 2 5 3 4 1 2 4 2 1 样例输出1 -1 3 选择语言 想法： 使用<vector>并进行优化(使用sort函数排序) 代码： #include<bits/stdc++.h> using namespace std; const int maxn= 20005; vector<int>vec[maxn]; int a[maxn]; bool flag[maxn]; int n,m; void init() { for(int i=1;i<n;i++) { for(int j=0;j<n;j+=i) vec[i].push_back(a[j]); } } int main() { int T; scanf("%d",&T); while(T--) { memset(flag,0,sizeof(flag)); scanf("%d%d",&n,&m); for(int i=0;i<n;i++) { scanf("%d",&a[i]); vec[i].clear(); } init(); int k,s; for(int i=0;i<m;i++) { scanf("%d%d",&k,&s); if(k>=n) { if(s==1) printf("%d\n",a[0]); else puts("-1"); continue; } if(vec[k].size()<s) //优化1 { puts("-1"); continue; } if(flag[k]==0) //优化2 { sort(vec[k].begin(),vec[k].end()); flag[k]=1; } printf("%d\n",vec[k][vec[k].size()-s]); } } return 0; }