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