调和序列(“盛大游戏杯”第15届上海大学程序设计联赛夏季赛暨上海高校金马五校赛（重现赛）)
发布时间: 2017年7月9日 20:20 时间限制: 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 个整数a 0 ,a 1 ,..,a n−1 ,0<=a i <2 31 , i=0,1,…,n−1 ，表示序列。 接下来m 行，每行两个整数K,S 0 < K <= 10 9 , 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
很早就有数学家研究,比如中世纪后期的数学家Oresme在1360年就证明了这个级数是发散的.他的方法很简单： 1 +1/2+1/3 +1/4 + 1/5+ 1/6+1/7+1/8 +… 1/2+1/2+(1/4+1/4)+(1/8+1/8+1/8+1/8)+… 注意后一个级数每一项对应的分数都小于调和级数中每一项,而且后面级数的括号中的数值和都为1/2,这样的1/2有无穷多个,所以后一个级数是趋向无穷大的,进而调和级数也是发散的. 从更广泛的意义上讲,如果An是不全部为0的等差数列,则1/An就称为调和数列,求和所得即为调和级数,易得,所有调和级数都是发散于无穷的. 编辑本段推导 随后很长一段时间,人们无法使用公式去逼近调和级数,直到无穷级数理论逐步成熟.1665年牛顿在他的著名著作《流数法》中推导出第一个幂级数： ln(1+x) = x - x^2/2 + x^3/3 - … Euler(欧拉)在1734年,利用Newton的成果,首先获得了调和级数有限多项和的值.结果是： 相关书籍 1+1/2+1/3+1/4+…+1/n= ln(n+1)+r(r为常量) 他的证明是这样的： 根据Newton的幂级数有： ln(1+1/x) = 1/x - 1/2x^2 + 1/3x^3 - … 于是： 1/x = ln((x+1)/x) + 1/2x^2 - 1/3x^3 + … 代入x=1,2,…,n,就给出： 1/1 = ln(2) + 1/2 - 1/3 + 1/4 -1/5 + … 1/2 = ln(3/2) + 1/2*4 - 1/3*8 + 1/4*16 - … . 1/n = ln((n+1)/n) + 1/2n^2 - 1/3n^3 + … 相加,就得到： 1+1/2+1/3+1/4+…1/n = ln(n+1) + 1/2*(1+1/4+1/9+…+1/n^2) - 1/3*(1+1/8+1/27+…+1/n^3) + . 后面那一串和都是收敛的,我们可以定义 1+1/2+1/3+1/4+…1/n = ln(n+1) + r Euler近似地计算了r的值,约为0.5772156649.这个数字就是后来称作的欧拉常数.不过遗憾的是,我们对这个常量还知之甚少,连这个数是有理数还是无理数都还是个谜.
简单的说最后的复杂度是一个比log 大一点的 log 所以总复杂度就是 n log log，然后就是一些边界了，傻瓜暴力
#include <bits/stdc++.h> using namespace std; vector<int> v[20010]; int num[20010]; bool comp(const int &a,const int &b) { return a>b; } int main() { int t; scanf("%d",&t); while(t--) { int n,m; scanf("%d%d",&n,&m); for(int i=0;i<n;i++) { scanf("%d",&num[i]); v[i].clear(); } for(int i=1;i<n;i++) { for(int j=0;j<=(n-1)/i;j++) { v[i].push_back(num[j*i]); } sort(v[i].begin(),v[i].end(),comp); } while(m--) { int k,s; scanf("%d%d",&k,&s); if(k>=n) { if(s==1) printf("%d\n",num[0] ); else printf("-1\n"); continue; } if(v[k].size()<s) printf("-1\n"); else printf("%d\n",v[k][s-1] ); } } }