本题是2021-12-1的延伸拓展,第一题如果没看过可以看我上一篇的题解:CCF CSP 2021-12-1 题解及满分代码(C++11)
问题描述
题目背景
上一题“序列查询”中说道:
A
=
[
A
0
,
A
1
,
A
2
,
⋯
,
A
n
]
A=[A0,A1,A2,⋯,An]
A=[A0,A1,A2,⋯,An] 是一个由 n+1 个 [0,N) 范围内整数组成的序列,满足
0
=
A
0
<
A
1
<
A
2
<
⋯
<
A
n
<
N
0=A0<A1<A2<⋯<An<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
)
⋅
x
N
f(x)≈(n+1)⋅xN
f(x)≈(n+1)⋅xN
为了方便计算,小 P 首先定义了比例系数
r
=
⌊
N
n
+
1
⌋
r=⌊\frac{N}{n+1}⌋
r=⌊n+1N⌋ ,其中 ⌊ ⌋ 表示下取整,即 r 等于 N 除以 n+1 的商。进一步地,小 P 用
g
(
x
)
=
⌊
x
r
⌋
g(x)=⌊\frac{x}{r}⌋
g(x)=⌊rx⌋ 表示自己估算出的 f(x) 的大小,这里同样使用了下取整来保证 g(x) 是一个整数。
显然,对于任意的询问 x∈[0,N),g(x) 和 f(x) 越接近则说明小 P 的估计越准确,后续进行线性查找的时间开销也越小。因此,小 P 用两者差的绝对值
∣
g
(
x
)
−
f
(
x
)
∣
|g(x)−f(x)|
∣g(x)−f(x)∣ 来表示处理询问 x 时的误差。
为了整体评估小 P 同学提出的方法在序列 A 上的表现,试计算:
e
r
r
o
r
(
A
)
=
∑
i
=
0
N
−
1
∣
g
(
i
)
−
f
(
i
)
∣
=
∣
g
(
0
)
−
f
(
0
)
∣
+
⋯
+
∣
g
(
N
−
1
)
−
f
(
N
−
1
)
∣
error(A)=\sum_{i=0}^{N−1}|g(i)−f(i)|=|g(0)−f(0)|+⋯+|g(N−1)−f(N−1)|
error(A)=i=0∑N−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 8
样例1输出
5
样例1解释
A
=
[
0
,
2
,
5
,
8
]
A=[0,2,5,8]
A=[0,2,5,8]
r
=
⌊
N
n
+
1
⌋
=
⌊
10
3
+
1
⌋
=
2
r=⌊\frac{N}{n+1}⌋=⌊\frac{10}{3+1}⌋=2
r=⌊n+1N⌋=⌊3+110⌋=2
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|
f(i) | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 3 | 3 |
g(i) | 0 | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 |
|g(i)−f(i)| | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
样例2输入
9 10
1 2 3 4 5 6 7 8 9
样例2输出
0
样例3输入
2 10
1 3
样例3输出
6
样例3解释
A
=
[
0
,
1
,
3
]
A=[0,1,3]
A=[0,1,3]
r
=
⌊
N
n
+
1
⌋
=
⌊
10
2
+
1
⌋
=
3
r=⌊\frac{N}{n+1}⌋=⌊\frac{10}{2+1}⌋=3
r=⌊n+1N⌋=⌊2+110⌋=3
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|
f(i) | 0 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
g(i) | 0 | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 3 |
|g(i)−f(i)| | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 |
子任务
70% 的测试数据满足 1≤n≤200 且
n
<
N
≤
1000
n<N≤1000
n<N≤1000;
全部的测试数据满足 1≤n≤105 且
n
<
N
≤
1
0
9
n<N≤10^9
n<N≤109。
提示
需要注意,输入数据 [A1⋯An] 并不一定均匀分布在 (0,N) 区间,因此总误差 error(A) 可能很大。
问题分析
本题题目背景和第一题相同,在第一题的基础上添加了两个新的条件:
- r = N/(n+1)
- g(x) = x/r
要求对于0—N-1的每一个取值x所对应的
∣
f
(
x
)
−
g
(
x
)
∣
|f(x)-g(x)|
∣f(x)−g(x)∣ 的值之和error
于是我们很快可以想到,第一题已经有快速简洁的方法求每一个f(x),那么在第一题的代码里再多求一个g(x),然后两者相减取个绝对值,这题不就结束了吗?太简单了!
但是经过实践,这样只能拿到70分
70分解法
#include<cstdio>
#include<cmath>
int main() {
int n, N;
scanf("%d %d", &n, &N);
int a[n+1];
int r = N/(n+1);
a[0] = 0;
for(int i=1; i<=n; i++) {
scanf("%d", &a[i]);
}
int fx, gx;
long long error = 0;
//计算f(i),i是0到N-1的正整数
int flag = 0; //用于指示数列a中值大于i的第一个下标
for(int i=0; i<N; i++) {
gx = i/r;
while(a[flag]<=i && flag<=n) {
flag++;
}
fx = flag-1;
error += abs(fx-gx);
}
printf("%lld", error);
return 0;
}
运行超时,因此还需优化时间复杂度。
满分解法
首先需要用到我们在第一题中发现的f(x)的规律,即对x
∈
\in
∈[ A[i],A[i+1]-1 ],f(x) = i
如果没有看可以先看一下第一题的优化解法:
CCF CSP 2021-12-1题解
然后我们观察一下g(x),因为g(x) = x/r,所以在x从0—N-1逐渐增大的过程中,g(x)的值是以r为间隔来变化的。
以样例1为例,我们在数组的最后再补一个值N:
可以看出,A[i]到A[i+1]-1之间的f(x)不变,而g(x)每r个数变一次值。
因此我们可以想到,以A[n+1]数组的下标为外层循环的变量,单次循环中f(i)值固定;内层循环以A[i]和A[i+1]-1为边界,将所有的g(x)值看成一个个长度为r的段,以这样的段位单位,每隔r个数计算一次g(x)和error,再对一些边界情况进行处理,即可实现优化。
代码如下:
#include<cstdio>
#include<cmath>
int main() {
long n;
long N;
scanf("%ld %ld", &n, &N);
long long r = N/(n+1);
long long a[100010];
a[0] = 0;
for(int i=1; i<=n; i++) {
scanf("%lld", &a[i]);
}
a[n+1] = N;
long long fx, gx; //fx,gx为当前计算的函数值
long long dr = r; //dr为内层循环每次要移动的位次
long long ddr = 0; //用于处理边界情况时的临时变量
int flag = 0; //用于标记dr是否改变
long long error = 0;
//以a[i]的值作为外层循环的界限
for(long long i=0; i<=n; i++) {
fx = i;
//在每段a[i]与 a[i+1]的间隔中,gx的值以r为间隔而变化
for(long long j=a[i]; j<a[i+1]; j=j+dr){
gx = j/r;
//上一个边界情况之后,上一段g(x)相等段中还有遗留未计算的部分,对其进行处理
if(flag == 1) {
dr = ddr;
flag = 0; //标记边界情况已处理完毕
}else {
dr = r; //边界情况处理完之后,重新将循环间隔变回r
}
//当前段处于a[i]和a[i+1]中间,直接计算error值
if(j+dr-1 < a[i+1]) {
error += abs(fx-gx)*dr;
}else { //j靠近a[i+1]的边界情况,即 j+dr-1 >= a[i+1]时
error += abs(fx-gx)*(a[i+1]-j);
ddr = dr-(a[i+1]-j); //记录当前g(x)值相同的长度为r的段内,尚未计算error值部分的长度
flag = 1; //标记当前段内有尚未计算error值的部分
}
}
}
printf("%lld", error);
return 0;
}
这一题我自己做的时候也只有70分,满分解法是参考了B站up主圣斗士-DS-ALGO的视频:202112(第24次)CSP真题202112-1,2讲解,视频讲的也比较清楚,没看懂题解的可以去看视频,可以点个赞支持一下原作者!
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)