题解分享
题解分享简介
等差数列 - 题解
解决思路
1. 好数序列分析：
- 如果公差 $D < 0$，序列递减，需将 $A$ 转化为第 $N$ 项的值，将 $D$ 取绝对值以便统一处理递增序列。
- 转化后，序列形式为 $A, A+D, A+2D, \ldots, A+(N-1)D$。
2. 二分查找：
- 将好数序列视为一个递增数组，使用二分查找定位 $X$ 在序列中的最近位置。
- 二分查找的目标是找到一个索引 $k$，使得 $A + k \cdot D$ 最接近 $X$。
3. 检查附近的项：
- 由于二分查找找到的位置可能不是最优解，还需检查二分附近的几项（例如 $k-1, k, k+1$），找出与 $X$ 的最小绝对差。
4. 时间复杂度：
- 构造序列的一般项计算复杂度为 $O(1)$。
- 二分查找的时间复杂度为 $O(\log N)$。
- 最多检查 10 项附近值，时间复杂度为常数级。
- 总复杂度为 $O(\log N)$。
代码详解
1. 输入数据预处理：
- 如果 $D < 0$，将序列起始值 $A$ 转化为最后一项 $A + (N-1)D$，并将 $D$ 取绝对值。
- 这样，序列转化为递增序列。
2. 二分查找：
- 定义查找范围为 $[0, N-1]$，取中间值计算该项对应的数值。
- 比较中间项和 $X$ 的大小，调整查找范围，直到找到最近的位置。
3. 周边值检查：
- 检查二分查找附近的几项（例如 $k-5$ 到 $k+5$，确保不越界），计算与 $X$ 的绝对差。
4. 输出结果：
- 输出最小绝对差。
```cpp
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
long long x, a, d, n;
cin >> x >> a >> d >> n;
// 处理递减序列，将其转为递增序列
if (d < 0) {
a = a + d * (n - 1);
d = -d;
}
// 二分查找最近的项
long long l = 0, r = n - 1;
while (l <= r) {
long long m = (l + r) / 2;
if (a + d * m < x) {
l = m + 1;
} else {
r = m - 1;
}
}
// 检查附近的项
long long res = LLONG_MAX;
for (long long i = max(0LL, l - 5); i <= min(n - 1, l + 5); i++) {
res = min(res, abs(a + d * i - x));
}
// 输出结果
cout << res << '\n';
return 0;
}
```
```java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long x = sc.nextLong();
long a = sc.nextLong();
long d = sc.nextLong();
long n = sc.nextLong();
// 转换递减为递增序列
if (d < 0) {
a = a + d * (n - 1);
d = -d;
}
// 二分查找最近的位置
long l = 0, r = n - 1;
while (l <= r) {
long m = (l + r) / 2;
if (a + d * m < x) {
l = m + 1;
} else {
r = m - 1;
}
}
// 检查附近的值
long res = Long.MAX_VALUE;
for (long i = Math.max(0, l - 5); i <= Math.min(n - 1, l + 5); i++) {
res = Math.min(res, Math.abs(a + d * i - x));
}
// 输出结果
System.out.println(res);
}
}
```
```python
def closest_good_number(x, a, d, n):
# 转换递减为递增序列
if d < 0:
a = a + d * (n - 1)
d = -d
# 二分查找最近的位置
l, r = 0, n - 1
while l <= r:
m = (l + r) // 2
if a + d * m < x:
l = m + 1
else:
r = m - 1
# 检查附近的值
res = float('inf')
for i in range(max(0, l - 5), min(n - 1, l + 5) + 1):
res = min(res, abs(a + d * i - x))
# 输出结果
return res
# 输入
x, a, d, n = map(int, input().split())
print(closest_good_number(x, a, d, n))
```
查看全文
0
0
0
3
