爱吃玉米的熊 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所有