求助,实际应用题目,多点到定点最短距离组
  • 板块题目总版
  • 楼主tnt191
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/9/15 00:19
  • 上次更新2024/9/15 11:15:59
查看原帖
求助,实际应用题目,多点到定点最短距离组
1457876
tnt191楼主2024/9/15 00:19

情景:带围巾是际霸2的游戏大厅地图作者。今天,他在编写一张游戏地图的规则时,遇到了难题:一局游戏中会有从3到14名不等的玩家加入这局游戏,并且随机出生在这张地图上。他想要编写的这条游戏规则,是将这些玩家尽量平均地分配到三个阵营里面交战。三个阵营各自有各自的主基地。他决定按照这些玩家到这个主基地的距离来为这些玩家分配队伍。而且要使得人数尽量均匀,才能让游戏相对公平。但是带围巾在着手解决这个问题的时候,被卡住了。你能帮帮他吗?

题目:在给定的坐标系(256*256)内,现在有3到14个随机的点(Xi,Yi),1<=i<=imax,3<=imax<=14,和3个固定点(Xpn,Ypn),1<=n<=3。不知道随机点和固定点的具体位置,但是你能够得到这3到14个点各自到这三个固定点的距离。请将这3到14个点根据它们到这三个点的距离,尽量均匀分配到三组,优先使得每组点到这组对应的固定点的距离之和最小,并且使得三组点的距离总和最小。每个点的到固定点的距离将会连续输入,输入三个数据之后换行。输出一组代表这个点的序号整数之后,请换行。

本题有多组数据

输入数据数量不固定,但是介于3到14组之间。

对于每组数据:

每一行三个整数 n,m,kn,m,k。 代表这一行对应的点到固定点的距离。

直至输入"over"。

输出每行包含一组代表点的数,数量不定,但介于1个到5个之间。

例子:(举例不是最优解)

输入:

1 3 9

2 4 6

235 63 26

200 30 200

152 16 46

28 94 56

1 3 9

2 4 6

235 63 26

200 30 200

152 16 46

28 94 56

0 255 255

over

输出:

1 2 7 8 13

4 5 6 9

3 10 11 12

2024/9/15 00:19
加载中...