Codeforces 1278 B. A and B （思维题）
发布时间
阅读量：
阅读量
题目链接：https://codeforces.com/contest/1278/problem/B
题目大意：
给定两个整数a,b，现在进行以下的操作：
第一次操作，从a,b两个数中选择一个+1。
第二次操作，从a,b两个数中选择一个+2。
第三次操作，从a,b两个数中选择一个+3。
....
问你最少需要多少步骤的操作，使得a,b两个整数相等？
思路：
为了使两数值相等, 我们必然努力弥补两者的差额. 将较小数值定义为a, 较大的数值定义为b, 并记录其差额记作del.
我们先将所有操作给到a身上，直到a>=b，此时有
newdel为新的差值。
- 如果newdel为偶数，我们考虑之前加在a上的值：1+2+3+...+k。如果现在我们不把一个数x加在a上，而是加在b上，那么对于上面的等式，是不是就相当于将newdel减去2x呢？也就是说，我可以通过改变之前的k个操作的位置，构造出任何小于k（k+1）的偶数的差！所以，此时答案就是k。
- 如果newdel为奇数，我们通过上面的方法只能构造出偶数，所以不能再向上面那样操作了。我们再在a上加上k+1，此时newdel=newdel+k+1，我们又可以接着利用上面的结论判断：
- 如果k+1为奇数，那么newdel+k+1为偶数，可以凑出来，答案就是k+1
- 如果k+1为偶数，那么newdel+k+1为奇数，此时仍然不能凑出来，但是k+2一定是奇数，newdel+k+2一定可以构造出来，所以答案就是k+2
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=100000+10;
int sum[maxn];
void init(){
sum[0]=0;
for(int i=1;i<maxn;i++){
sum[i]=sum[i-1]+i;
}
}
signed main(){
int T;
init();
scanf("%lld",&T);
while(T--){
int a,b;
scanf("%lld%lld",&a,&b);
int del=abs(a-b);
if(del==0){
puts("0");
continue;
}
int ans=0;
int inx=0;
for(int i=1;i<maxn;i++){
if(sum[i]>=del){
ans=sum[i];
inx=i;
break;
}
}
if(ans==del){
printf("%lld\n",inx);
}
else{
int now=ans-del;
if(now%2==0){
printf("%lld\n",inx);
}
else{
if((inx+1)%2==0){
printf("%lld\n",inx+2);
}
else{
printf("%lld\n",inx+1);
}
}
}
}
return 0;
}
/*
100
1 1000000000
999999999 1
1 999999998
999999997 1
1 999999996
999999995 1
1 999999994
999999993 1
1 999999992
999999991 1
1 999999990
999999989 1
1 999999988
999999987 1
1 999999986
999999985 1
1 999999984
999999983 1
*/
AI写代码全部评论 (0)
还没有任何评论哟~