問題四

Q4.
  這是一片三角形樹林,我們給每顆數編號如下圖。如今這片樹林裡有些樹木生病了!如下圖,編號6、9、14、19號樹木生病,我們必需找出範圍最小的三角形樹林將之隔離。

ntucsie2008pro4.png

輸入
首先是整數N代表有幾顆樹生病,生病的樹將由小排到大。
輸出
最小三角形的三個頂點


範例輸入
4
6 9 14 19
範例輸出
6 18 21


解題關鍵

我的解題方法與概念是,先對於每個輸入的點找到他在圖形中的所在地,利用(行,右,左)的方法來表現其位置,詳細方法不贅述,程式碼中有解。

為了方便,我在程式一開始宣告了一個陣列儲存了每行開頭的數字(a陣列),利用此陣列,以及上述概念,可以發現需要輸出的三個頂點分別為(a[左+又-1]+右-1)(a[最大行]+右-1)(a[最大行]+ 最大行-1)

詳細關係可以慢慢揣摩揣摩,有疑問可以問問電腦老師或我XD

特別感謝mTwTm(小天)提供多組測資及Debug!

程式碼參考

#include <stdio.h>
#include <stdlib.h>

int main()
{
   int i,j,k;
   int max=10001;
   int a[10001]={0};
   int leftmin,rightmin,linemax;
   
   for(i=0;i<max-1;i++){   
      a[i+1]=1+(i*(i+1))/2;
   }   
   
   while(scanf("%d",&i)!=EOF){
   
   int n[i];
   
   for(j=0;j<i;j++){
      scanf("%d",&n[j]);
   }
   
   leftmin=rightmin=max;
   
   linemax=0;
   
   for(j=0;j<i;j++){
      
      k=1;
      
      while(n[j]>=a[k]){
         k++;      
      }
      
      k--; 
   
      if(k>linemax) linemax=k;
   
      if((n[j]-a[k]+1) < rightmin) rightmin=n[j]-a[k]+1;
   
      if(k-n[j]+a[k] < leftmin) leftmin=k-n[j]+a[k];
                        
   }   
   
printf("%d %d %d\n",a[leftmin+rightmin-1]+rightmin-1,
a[linemax]+rightmin-1,a[linemax]+linemax-leftmin); 
  
   }
   /* system("PAUSE");*/
   return 0;
}

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s

%d 位部落客按了讚: