Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

你们难道都不知道1+2+..+n-1+n+n-1+...+2+1 = n^2吗

Posted by Eov_Second at 2016-12-02 00:50:54 on Problem 2590
从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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator