愛吃玉米的熊 XTU1122

Description

題目描述

GB是隻可愛的熊寶寶，它最喜歡吃玉米了，是以每次看到玉米，它就迫不及待的沖過去。 現在有n個玉米，GB每次都會去吃離它最近的玉米(吃完後會移動到玉米的位置)，請問GB吃玉米的順序是什麼？

輸入

第一行給出樣例個數T。對于每個樣例，第一行給出n，玉米數目。之後的n行給出玉米的坐标x，y。 最後一行給出GB開始的坐标。樣例保證任何時候離GB最近的玉米是唯一。 所有坐标0 ≤ x , y ≤ 10000 n <= 1000

輸出

對于每個樣例輸出一行，輸出吃玉米的順序，每個序号（序号從1開始）之間有一個空格。

樣例輸入

2

3

1 1

2 2

3 3

0 0

3

0 3

0 2

0 1

0 0

樣例輸出

1 2 3

3 2 1

Source:

2012年下學期《程式設計實踐》期中考試

CodeAuthor:IronChen

比較複雜的思路：用優先隊列priority_queue的周遊完成。

wrong answer code:

#include<iostream>
#include<queue>
using namespace std;
const int MAXN = 1053;
struct node{
 int x, y, dist, id;
 node(int _x, int _y, int _dist, int _id){
  x = _x, y = _y, dist = _dist, id = _id; 
 }
};
priority_queue<node> yumi;
int main(){
 ios::sync_with_stdio(false);
 int T;
 cin>>T;
 while(T--){
  int n;
  cin>>n;
  int x, y;
  for(int i  = 1; i <= n; i++){
   cin>>x>>y;
   yumi.push(node(x, y, 0, i));
  }
  int GB_x, GB_y;
  cin>>GB_x>>GB_y;
   for(int i = 1; i <= n; i++){
   int minDist = -1;
   priority_queue::iterator it;
   for(it = yumi.begin(); it != yumi.end(); it++){
    node tmp = *it;
    tmp.dist = (tmp.x-GB_x)*(tmp.x-GB_x)+(tmp.y-GB_y)*(tmp.y-GB_y);
   }
   node ans = yumi.top();
   yumi.pop();
   if(i == 1) cout<<ans.id;
   else cout<<" "<<ans.id;
   GB_x = ans.x, GB_y = ans.y;
  }
  cout<<endl;
 }
}
  
           

Accepted Code:

每按照最小序号cnt到最大序号n+1排序一次，選取距離排序最小的序号cnt輸出，GB的位置移到最小位置點，cnt++。這樣就能除去已輸出的最短位置。

#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 1053;
struct node{
 int x, y, dist, id; 
}yumi[MAXN];//定義結構體
bool cmp(node a, node b){//定義排序函數，資料比較 
 return a.dist < b.dist;
}
int main(){
 ios::sync_with_stdio(false);//運算加速 
 int T;
 cin>>T;
 while(T--){
  int n;
  cin>>n;
  
  for(int i  = 1; i <= n; i++){
   cin>>yumi[i].x>>yumi[i].y;//玉米位置 
   yumi[i].id = i;
  }
  int GB_x, GB_y;
  cin>>GB_x>>GB_y;// 熊的初始位置 
  
  int cnt = 1;
  for(int i = 1; i <= n; i++){
   for(int j = cnt; j <= n; j++){
    yumi[j].dist = (GB_x-yumi[j].x)*(GB_x-yumi[j].x)+(GB_y-yumi[j].y)*(GB_y-yumi[j].y);
   }
   sort(yumi+cnt, yumi+n+1, cmp);//排序 
   if(i == 1) cout<<yumi[cnt].id;
   else cout<<" "<<yumi[cnt].id;
   GB_x = yumi[cnt].x, GB_y = yumi[cnt].y;
   cnt++;//除去最近的數 
  }
  cout<<endl;
 } 
}


           

本文由部落客整理而成，代碼著作權與最終解釋權歸IronChen所有