最近我在掙扎，都工作的人了還念念不忘ACM，是不是太閑了！?。∥野l現我喜歡數學，我喜歡做邏輯一點的事情，不會很復雜，一切符合邏輯了才好處理。。。
不扯淡了！看下題目吧！
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) //偶數減回去?。。?/span>
len--;
printf("%I64d\n",len);
}
}
return 0;
}
posted on 2010-08-29 17:03
jince 閱讀(834)
評論(0) 編輯 收藏 引用 所屬分類:
Questions