简答题
偏难
#13109
最佳操作数 题目描述 给定一个数字 x,再给定一个等差数列。请寻找这个等差数列距离 x 最近的数字,并输出这个最小距离。 等差数列的第一项叫做首项,用数字 a…
最佳操作数
题目描述
给定一个数字 x,再给定一个等差数列。请寻找这个等差数列距离 x 最近的数字,并输出这个最小距离。
等差数列的第一项叫做首项,用数字 a 表示,接下来每一项都比前一项多 d,d 称之为公差,数列的项数记为 n。
输入
输入四个整数分别表示 x、a、d、n。
输出
输出一个整数表示最少的操作次数。
数据范围
-10^18≤x、a≤10^18,-10^6≤d≤10^6,1≤n≤10^12。
输入样例1
3 1 3 3
输出样例1
1
输入样例2
-1000000000000000000 1 3 3
输出样例2
1000000000000000001
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <bits/stdc++.h>
using namespace std;
int main() {
long long x, a, d, n;
cin >> x >> a >> d >> n;
if(d==0) { //公差为0
cout << abs(x-a);
} else {
long long L=a; //左边界
long long R=a+(n-1)*d; //右边界
if(d < 0)
swap(L, R);
if(x <= L) {
cout << abs(L-x);
} else if(x>=R) {
cout << abs(R-x);
} else {
long long k = (x - a) / d; //最接近的项
//比较邻近的第k-1项,k项和k+1项
long long minDelta=abs(a+k*d-x);
if(k-1>=0)
minDelta=min(minDelta, abs(a+(k-1)*d-x));
if(k+1<n)
minDelta=min(minDelta, abs(a+(k+1)*d-x));
cout << minDelta;
}
}
return 0;
}</pre>
这道题暂未补解析。