#P2021122. 序列查询新解
序列查询新解
序列查询新解
题目描述
题目背景
上一题“序列查询”中说道: A=[A0,A1,A2,⋯,An]是一个由n+1个[0,N)范围内整数组成的序列,满足0=A0<A1<A2<⋯<An<N。基于序列A,对于[0,N)范围内任意的整数x,查询f(x)定义为:序列A中小于等于x的整数里最大的数的下标。
对于给定的序列A和整数x,查询f(x)是一个很经典的问题,可以使用二分搜索在O(logn)的时间复杂度内轻松解决。但在 IT 部门讨论如何实现这一功能时,小 P 同学提出了些新的想法。
题目描述
小 P 同学认为,如果事先知道了序列A中整数的分布情况,就能直接估计出其中小于等于x的最大整数的大致位置。接着从这一估计位置开始线性查找,锁定f(x)。如果估计得足够准确,线性查找的时间开销可能比二分查找算法更小。
比如说,如果A1,A2,⋯,An均匀分布在(0,N)的区间,那么就可以估算出: f(x)≈(n+1)⋅xN
为了方便计算,小 P 首先定义了比例系数r=⌊Nn+1⌋,其中⌊⌋表示下取整,即r等于N除以n+1的商。进一步地,小 P 用g(x)=⌊xr⌋表示自己估算出的f(x)的大小,这里同样使用了下取整来保证g(x)是一个整数。
显然,对于任意的询问x∈[0,N),g(x)和f(x)越接近则说明小 P 的估计越准确,后续进行线性查找的时间开销也越小。因此,小 P 用两者差的绝对值|g(x)−f(x)|来表示处理询问x时的误差。
为了整体评估小 P 同学提出的方法在序列A上的表现,试计算: error(A)=∑i=0N−1|g(i)−f(i)|=|g(0)−f(0)|+⋯+|g(N−1)−f(N−1)|
输入格式
从标准输入读入数据。
输入的第一行包含空格分隔的两个正整数n和N。
输入的第二行包含n个用空格分隔的整数A1,A2,⋯,An。
注意A0固定为0,因此输入数据中不包括A0。
输出格式
输出到标准输出。
仅输出一个整数,表示error(A)的值。
数据范围
(原站未提供,导入后需人工补齐)
样例
3 10
2 5 8
5
9 10
1 2 3 4 5 6 7 8 9
0
2 10
1 3
6
提示
样例1解释
A=[0,2,5,8]
r=⌊N/n+1⌋=⌊10/3+1⌋=2
i0123456789
f(i)0011122233
g(i)0011223344
|g(i)−f(i)|0000101111
子任务
70%的测试数据满足1≤n≤200且n<N≤1000;
全部的测试数据满足1≤n≤105且n<N≤109。
提示
需要注意,输入数据[A1⋯An]并不一定均匀分布在(0,N)区间,因此总误差error(A)可能很大