渭城朝雨浥卿澄

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

輸入
首先是整數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;
}