目录
1.C - ±1 Operation 1
题意
一个操作是指给一个数加上1或者减掉1.若有个等差数列
有
个元素，第一个元素为
，其中的任意一个数叫做好数。请将数
进行0次或以上操作，使其成为好数。那么最少需要多少次操作？
思路
????????1.处理递减序的情况。
只要按下面代码就能编程递增序。就是把第一个变为最后，最后变为第一个。倒序一下数列。
if(d<0){
long long fi=a+d*(n-1);
a=fi;
d*=-1;
}接下来有两种解法将会阐述。请选择适合的一种方法。
??????? 2.二分查找
序列包括了所有整数
的
。当
，序列S就是递增的，所以我们可以通过在
上进行二分找
，查找离
最近的元素。就是二分答案。代码在后面。现在介绍另外一种方法。
??????? 3.分类讨论
类似于数学思想。定义,
，分别为数列中最小与最大的元素。开始分类：
??????? 1.如果在start与final之间：
- 如果公差为0，那所有数都是一样的，因而求出答案为0.
- 否则，对于每个K都满足
，数列S包括了
，并且
,所以答案为
。这是在把零头比小。因为你也不知道是靠上还是靠下。如果除数为10，模数为1，那么向下；而模数若为8，那么靠上。所以诞生了这条语句。
??????? 2.如果在start之前：
??????? 答案为start-X；
??????? 3.如果X在final后：
??????? 答案为X-final；
程序
??????? 方法1：二分查找
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void)
{
long long x,a,d,n;
cin >> x >> a >> d >> n;
if(d<0)
{
ll fi=a+d*(n-1);
a=fi;
d*=-1;
}
ll st=0,fi=(n-1);
while(st<=fi)
{
ll mid=(st+fi)/2;
if(a+d*mid<x)
st=mid+1;
else
fi=mid-1;
}
ll res=8e18;
for(ll i=max(0ll,st-5); i<=min(n-1,st+5);i++)
res=min(abs(a+d*i-x),res);
cout<< res;
return 0;
}???????? 方法2：分类讨论
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,x,d,n;
int main(void)
{
cin>> x>> a>> d>> n;
if(d<0)
{
ll fi=a+d*(n-1);
a=fi;
d*=-1;
}
ll st=a,fi=a+d*(n-1);
if(x>=st && x<=fi)
{
ll m;
if(d!=0)
m=(x-st)%d;
else
m=0;
cout<<min(m,d-m);
}
else if(x<st) cout<<st-x;
else cout<<x-fi;
return 0;
}?Bye bye！（蒟蒻作此文，有刺快来挑！）