| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
你们难道都不知道1+2+..+n-1+n+n-1+...+2+1 = n^2吗从1加到n再加回1正好是n的平方,这是小学就知道的东西啊。
这题先看x,y差值,如果正好是k平方,那就是2k-1步
否则求最大的k,使得k*k<y-x,那么至少是有2k-1步,因为y - x和k*k的差值最大也就是2k,所以剩下的差距(y - x - k*k)如果比k大,那么需要两个数补齐,否则补一个数就行了。
举个例子,如果y - x = 34,那么求出k=5,所以至少有2*5-1=9个数。还剩下34 - 25 = 9个距离,补一个5,补一个4就行了,那么最后的序列为
1 2 3 4 5 (5) 4 (4) 3 2 1 括号内的表示补齐的数字
最后上代码
int main()
{
int t;
unsigned int x, y,k,a,b,c;
scanf("%d",&t);
while(t--){
scanf("%u %u", &x, &y);
k = y - x;
if(0==k)c = 0;
else{
a = (unsigned int)sqrt((double)k);
b = a * a;
if(b == k) c = 2*a - 1;
else if(k>a+b)
c = 2*a + 1;
else
c = 2*a;
}
printf("%u\n",c);
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator