---

第4測資逾時，不曉得改優化輸入有幫助嗎？ 或者將 STL的set部份另寫有幫助？

請熱心高手幫忙給個提示，謝了！

第 1 測資點(50%): AC (92ms, 220KB)
通過檢測

第 2 測資點(20%): AC (1.2s, 236KB)
通過檢測 第 3 測資點(20%): AC (0.8s, 212KB)
通過檢測 第 4 測資點(5%): TLE (3s)
執行逾時

Killed 

第 5 測資點(5%): AC (2.1s, 268KB)
通過檢測

// b348: 最近餐館
#include <iostream>
#include <cstring>
#include <set>
#define LLI long long int
using namespace std;
const int maxn = 8192;
const int dimk = 6;
LLI x[maxn][dimk] ;
LLI m[dimk];
set < LLI > ans;
set < LLI >::iterator it;
set < LLI >::reverse_iterator rit;
int main()
{
  int i,j,n,k , q,p;
  int cas=0;
 while( cin >> n >> k )
 {
  for(i=0;i<n;++i)    // 讀入 n 間餐廳的座標 x[0][0]~x[n-1][k-1]
   for(j=0;j<k;++j) cin >>x[i][j]; 
  cin >> q;
  while( q-- ) // q組詢問，每組兩列，第1列 m 的座標 k 個， 第2列 要顯示的 p 個餐廳
  {
   ans.clear();   // 以 set 存放 最近的 p 個餐廳 (距離^2)*10000+編號
   for(j=0; j<k; ++j) cin >> m[j];   // m 的 k維座標
   cin >> p;
   LLI  d0=0x7fffffffffffffffll;   //目前在 set內排名最後的餐廳
   for(i=0;i<n; ++i)       //計算 n 個餐廳與 m 的距離
   {
    LLI dd=0 ,dx;
    for(j=0; j<k; ++j)
    {
     dx = m[j] - x[i][j];
     dd += dx*dx;
    }
    dd = dd*10000 + i;
    if(ans.size()<p || dd<=d0)
    {
     if(ans.size()>=p) // p 個了, 只留最優先的 p 個
     {
      rit = ans.rbegin(); 
      ans.erase((*rit));
     } 
     ans.insert(dd);
     rit = ans.rbegin();
     d0 = (*rit);
    }     
   } 
   cout << "Case " << ++cas <<": " << p;
   for(i=0,it=ans.begin(); i<p; ++i,++it) cout << " " << (*it) % 10000 +1;
   cout << endl;
  }
 }
  return 0;
}

 

 

---

只要比單筆 $$O(n)$$ 稍微來得快就可以，需要比較有結構化的空間結構來協助。 

---

 謝謝，我又仔細看了一下題目，好像要使用KD-Tree之類的結構，
 凡人與神確有一段距離，想要再近一點，不知要看什麼書？

 

---

不會啦，我們距離很近的，這些抓到小概念，實作上努力一下就可以。

如果不排斥英文，可以參考一下

關於計算幾何的資料結構可以去看 Computational Geometry Algorithms and Applications, 3rd Ed - de Berg et al 這本書，下載。

另外可以去搜索 Advanced Data Structures - Mit 課程內容，也能學到不少特殊的資料結構。

我從別人口中聽來的居多，沒有細看上面幾個書本、課程內容。

 

---

　非常謝謝，我會努力的！