体育游戏获胜者预测 - C++ 算法实现

"题目描述：\n上了半天的物理数学课，大家的脑子有点转不动了，下午的课表似乎看透了同学们的心思，第一节就安排了体育课，CZ中学的课表真是太有爱了，赞一个！午间休息后，文体委员小S喊大家到教室外的走廊上排队，队形整好后小S带着大家走到了大操场上，体育老师早就在那等着了，他先安排同学们做了五分钟的准备活动，接下来让大家玩一个有趣的游戏，在这个游戏里，全班同学先散开站在操场上，同学们轮流玩这个游戏，从1号同学开始，然后是2号3号等等（只要这个同学仍然参与这个游戏）。每次轮到玩的同学，就选择一个目前离他最近的同学，走过去拍他一下，然后回到原来的位置，那个被拍到的同学就被排除在游戏之外了，必须立刻离开操场。当操场上只剩下一个同学时，游戏即告结束，最后站在操场上的那个同学就是嬴家。\nR老师正和隔壁班的F主任津津有味地在场边看着同学们做游戏，为了添加一点乐趣，R老师就和F主任打赌哪个同学会嬴？所以他想事先知道谁是嬴家。R老师希望你写一个程序，读入同学们相互之间的距离，模拟出哪个同学最终会获胜。\n输入: 输入数据第一行为一个正整数N,表示在操场上玩游戏的人数，其中1WNS1000,接下来共有N行数据，每行有N个用空格隔开的整数，其中第i行\n 第j列的数据表示操场上编号为i的同学与编号为j的同学之间的距离。输入数据保证第i行第i列（主对角线上的位置）的数据均为0,其余数据均为正整\n 数，且第i行第J列的数据一定等于第J行第i列的数据，这意味着同学甲到同学乙的距离等于同学乙到同学甲的距离；操场上任意两对同学之间的距离均\n 不相同，也就是说上三角部分的正整数互不相同。\n输出: 输出数据仅有一行包含一个正整数表示获胜的同学的编号。\n样例1：输入 \n4\n0 1 6 3\n1 0 4 5\n6 4 0 2\n3 5 2 0\n样例1：输出\n1\n用C++，尽量降低时间复杂度，确保答案正确内容：思路：\n首先，我们可以使用一个数组来存储每个同学的编号和其在操场上的位置。然后，我们可以使用一个循环来模拟每个同学玩游戏的过程。在每一轮中，我们找到距离当前同学最近的其他同学，将其从数组中删除。最后，当数组中只剩下一个元素时，该元素即为获胜的同学的编号。\n具体步骤如下：\n1. 读取输入的人数N。\n2. 创建一个大小为N的数组，用于保存同学的编号和在操场上的位置。\n3. 使用两个嵌套循环，分别遍历数组中的每个同学和其他同学，计算他们之间的距离，并更新最小距离和最近同学的位置。\n4. 在每一轮循环中，找到距离当前同学最近的其他同学，将其从数组中删除。\n5. 当数组中只剩下一个元素时，输出该元素即为获胜的同学的编号。\n代码如下：\n\ncpp\n#include <iostream>\n#include <vector>\nusing namespace std; \n\nint main() {\n int N; \n cin >> N; \n \n vector<pair<int, int>> students(N); // 保存同学的编号和位置\n for(int i = 0; i < N; i++) {\n students[i].first = i + 1; // 同学的编号从1开始\n }\n \n vector<vector<int>> distance(N, vector<int>(N));\n for(int i = 0; i < N; i++) {\n for(int j = 0; j < N; j++) {\n cin >> distance[i][j];\n }\n }\n \n while(students.size() > 1) {\n int minDistance = INT_MAX; \n int closestStudent = -1; \n \n for(int i = 0; i < students.size(); i++) {\n int currentStudent = students[i].second; \n \n for(int j = 0; j < N; j++) {\n if(j != currentStudent && distance[currentStudent][j] < minDistance) {\n minDistance = distance[currentStudent][j];\n closestStudent = j;\n }\n }\n }\n \n for(auto it = students.begin(); it != students.end(); ) {\n if(it->second == closestStudent) {\n it = students.erase(it);\n } else {\n it++;\n }\n }\n }\n \n cout << students[0].first << endl; \n \n return 0; \n}\n\n\n该算法的时间复杂度为O(N^2)，其中N为同学的人数。\n