发布时间: 2017年7月9日 18:17 最后更新: 2017年7月9日 21:05 时间限制: 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 #include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<ctype.h> #include<math.h> #include<set> #include<map> #include<vector> #include<queue> #include<bitset> #include<algorithm> #include<time.h> using namespace std; void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); } #define MS(x, y) memset(x, y, sizeof(x)) #define ls o<<1 #define rs o<<1|1 typedef long long LL; typedef unsigned long long UL; typedef unsigned int UI; template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; } template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; } const int N = 20020, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f; template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; } int casenum, casei; int n, m; int a[N]; vector<int>vt[N]; int main() { scanf("%d", &casenum); for (casei = 1; casei <= casenum; ++casei) { scanf("%d%d", &n, &m); for (int i = 0; i < n; ++i) { scanf("%d", &a[i]); vt[i + 1].clear(); } for (int K = 1; K <= n; ++K) { for (int x = 0; x < n; x += K) { vt[K].push_back(a[x]); } sort(vt[K].begin(), vt[K].end()); reverse(vt[K].begin(), vt[K].end()); } while (m--) { int K, S; scanf("%d%d", &K, &S); if (K > n) { if (S == 1) { printf("%d\n", a[0]); } else { puts("-1"); } continue; } if (vt[K].size() < S) { puts("-1"); } else { printf("%d\n", vt[K][S - 1]); } } } return 0; } /* 【题意】 http://acmoj.shu.edu.cn/problem/417/ 【分析】 因为for(i=1~n)for(j=i的倍数 && j<=n)的复杂度是nlogn 所以直接预处理就好了。 但是因为这里下标是从0开始，小心一下K比较大特殊情况就好啦。 */