序列查询新解
题目背景
上一题“序列查询”中说道：
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) 的值。
样例1输入
3 10
2 5 8Data
样例1输出
5
思路：对于枚举的区间[a[i - 1], a[i] - 1)，计算出其gx的取值范围，然后按gx去分段，因为当前区间的所有x，其fx = i - 1。
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define endl '\n'
#define rep(i,a,n) for (int i = a; i < n; i ++ )
#define repn(i,a,n) for (int i = a; i <= n; i ++ )
#define pb push_back
#define IOS ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
ll gcd(ll a,ll b) { return b ? gcd(b,a % b) : a; }
const int mod = 1e9+7;
int n, k;
const int N = 100010;
int a[N];
ll ans;
int main()
{
IOS;
cin >> n >> k;
repn(i, 1, n)
cin >> a[i];
a[n + 1] = k;
int t = k / (n + 1);
for (int i = 1; i <= n + 1; i ++ )
{
ll l = a[i - 1], r = a[i] - 1;//枚举区间[l, r);
ll gl = l / t, gr = r / t;
ll x = i - 1;
//将每一段分成三部分：
//最开始的部分，中间部分，最后的部分
//最开始和最后部分可能不完整
//也可能开始部分和最后部分是一个数
if(gl == gr)//如果开始和最后部分相同
{
ans += (r - l + 1) * labs(gr - x);
}
else//加上开始部分和最后部分
{
ans += (t - (l % t)) * labs(gl - x);
ans += (r % t + 1) * labs(gr - x);
}
//加上中间完整的部分
for (int j = gl + 1; j < gr; j ++ ) ans += t * labs(j - x);
}
cout << ans << endl;
return 0;
}