最近我在掙扎，都工作的人了還念念不忘ACM，是不是太閑了！！！我發(fā)現(xiàn)我喜歡數(shù)學(xué)，我喜歡做邏輯一點(diǎn)的事情，不會(huì)很復(fù)雜，一切符合邏輯了才好處理。。。
不扯淡了！看下題目吧！
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
這是我大學(xué)里真正老師教的第一個(gè)題目，在我映像里老師很犀利，幾句話就把題目意思和解題思路講清楚了，老師追求的是效率，現(xiàn)在想起來(lái)是這樣的！但是我當(dāng)時(shí)并沒(méi)有怎么聽懂，回去也沒(méi)好好研究過(guò)，直到后來(lái)老師給答案了才粗粗的看了一下，知道了解題思路，但是自己又沒(méi)去寫過(guò)，再后來(lái)有一天我發(fā)現(xiàn)了這個(gè)題目把它干掉了。。。
題目大意：從右側(cè)三角中任去兩個(gè)數(shù)，求他們之間的最短路勁。例如取出3和7他們之間的最短路勁為3，6到12他們之間的最短路勁為3。。
解題思路：
1、很明顯我們可以求出給出的兩個(gè)數(shù)的行號(hào)和列號(hào)；
2、思考怎么走才算是最短，在一個(gè)三角形中頂點(diǎn)上的數(shù)走到下邊行中的奇數(shù)列的最短路徑是相等的，例如：1走到2，4；1走到5，7，9；1走到11，13，15；偶數(shù)列也同樣！根據(jù)這一點(diǎn)我們可以用較小的數(shù)構(gòu)造一個(gè)最小上三角，然后一層層往下映射，求出最短路勁，直到到達(dá)較大數(shù)所在行！如果該數(shù)在映射三角中，直接輸出，否者，從映射三角的最右端或者最左端往右走或者往左走！
寫代碼的時(shí)候需要注意的幾點(diǎn)：
1、M，N的數(shù)據(jù)比較大，在計(jì)算的時(shí)候可能會(huì)超出int范圍，最好用__int64;
2、構(gòu)造三角的時(shí)候，如果較小數(shù)在奇數(shù)列，可以直接向下映射，如果是偶數(shù)的話，可以向上翻，最后結(jié)果減1就行；
3、事實(shí)上我們可以根據(jù)已知行號(hào)和列號(hào)，直接求得在大數(shù)行上的映射三角的最短路勁；
代碼如下（老師給的）：
#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;
}
//求的行號(hào)和列號(hào)
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)); //求的三角形頂點(diǎn)數(shù)，偶數(shù)的往上翻一下
tlm=leve(tm);
ml=tm+(ln+tlm-2)*(ln-tlm); //求得映射三角在較大數(shù)所在行的最左側(cè)數(shù)
mr=tm+(ln+tlm)*(ln-tlm); //求得映射三角在較大數(shù)所在行的最右側(cè)數(shù)
if(ml<=n&&n<=mr) //若較大數(shù)在區(qū)間內(nèi)，則求的結(jié)果
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) //偶數(shù)減回去！！！
len--;
printf("%I64d\n",len);
}
}
return 0;
}
posted on 2010-08-29 17:03
jince 閱讀(810)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
Questions