最近我在挣扎，都工作的人了还念念不忘ACM，是不是太闲了！！！我发现我喜欢数学，我喜欢做逻辑一点的事情，不会很复杂，一切符合逻辑了才好处理。。。
不扯淡了！看下题目吧！
Description
A triangle field is numbered with successive integers in the way shown on the picture below.
The traveller needs to go from the cell with number M to the cell with number N. The traveller is able to enter the cell through cell edges only, he can not travel from cell to cell through vertices. The number of edges the traveller passes makes the length of the traveller's route.
Write the program to determine the length of the shortest route connecting cells with numbers N and M.
Input
Input contains two integer numbers M and N in the range from 1 to 1000000000 separated with space(s).
Output
Output should contain the length of the shortest route.
Sample Input
6 12
Sample Output
3
Source
Ural Collegiate Programming Contest 1998
这是我大学里真正老师教的第一个题目，在我映像里老师很犀利，几句话就把题目意思和解题思路讲清楚了，老师追求的是效率，现在想起来是这样的！但是我当时并没有怎么听懂，回去也没好好研究过，直到后来老师给答案了才粗粗的看了一下，知道了解题思路，但是自己又没去写过，再后来有一天我发现了这个题目把它干掉了。。。
题目大意：从右侧三角中任去两个数，求他们之间的最短路劲。例如取出3和7他们之间的最短路劲为3，6到12他们之间的最短路劲为3。。
解题思路：
1、很明显我们可以求出给出的两个数的行号和列号；
2、思考怎么走才算是最短，在一个三角形中顶点上的数走到下边行中的奇数列的最短路径是相等的，例如：1走到2，4；1走到5，7，9；1走到11，13，15；偶数列也同样！根据这一点我们可以用较小的数构造一个最小上三角，然后一层层往下映射，求出最短路劲，直到到达较大数所在行！如果该数在映射三角中，直接输出，否者，从映射三角的最右端或者最左端往右走或者往左走！
写代码的时候需要注意的几点：
1、M，N的数据比较大，在计算的时候可能会超出int范围，最好用__int64;
2、构造三角的时候，如果较小数在奇数列，可以直接向下映射，如果是偶数的话，可以向上翻，最后结果减1就行；
3、事实上我们可以根据已知行号和列号，直接求得在大数行上的映射三角的最短路劲；
代码如下（老师给的）：
#include<stdio.h>
#include<math.h>
__int64 leve(__int64 x)
{
double y;
__int64 k;
if(x==1)
return 1;
else
{
y=sqrt(x);
k=sqrt(x);
if(y==k)
return k;
else
return k+1;
}
}
int main()
{
__int64 n,m,temp,ln,lm,pm,pn,tm,mr,ml,tlm,len;
while(scanf("%I64d %I64d",&m,&n)!=EOF)
{
if(m>n)
{
temp=n;
n=m;
m=temp;
}
//求的行号和列号
lm=leve(m);
ln=leve(n);
pm=m-(lm-1)*(lm-1);
pn=n-(ln-1)*(ln-1);
if(lm==ln) //同行，直接输出
printf("%I64d\n",pn-pm);
else
{
tm=(pm%2)?m:(m-2*(lm-1)); //求的三角形顶点数，偶数的往上翻一下
tlm=leve(tm);
ml=tm+(ln+tlm-2)*(ln-tlm); //求得映射三角在较大数所在行的最左侧数
mr=tm+(ln+tlm)*(ln-tlm); //求得映射三角在较大数所在行的最右侧数
if(ml<=n&&n<=mr) //若较大数在区间内，则求的结果
len=(pn%2)?(2*(ln-tlm)):(2*(ln-tlm)-1);
else //否则再向左走或者向右走
{
len=2*(ln-tlm);
if(n<ml)
len+=(ml-n);
if(n>mr)
len+=(n-mr);
}
if(pm%2==0) //偶数减回去！！！
len--;
printf("%I64d\n",len);
}
}
return 0;
}
posted on 2010-08-29 17:03
jince 阅读(732)
评论(0) 编辑 收藏 引用 所属分类:
Questions