华为校招机试

2024-07-16 07:36| 来源: 网络整理| 查看: 265

在线OJ测试

题目详情 - 足球队员射门能力排序 - HydroOJ

题目描述

球队有 n 个足球队员参与 m 次射门训练

每次射门进球用 1 表示，射失则用 0 表示，依据如下规则对该 n 个队员的射门能力做排序：

进球总数更多的队员射门能力更强若进球总数—样多，则比较最多—次连续进球的个数，最多的队员能力更强若最多一次连续进球的个数一样多，则比较第一次射失的先后顺序，其中后射失的队员更强，若第一次射失顺序相同，则按继续比较第二次射失的顺序，后丢球的队员能力更强，依次类推若前3个规则排序后，还能力相等，则队员编号更小的能力更强

输入描述

第 1 行：足球队员数 n，射门训练次数 m

队员编号从 1 开始，依次递增n 和 m 均为正整数0 < n ≤ 10^30 < m ≤ 10^3

第 2 行：第 1 ~ n 个队员从第 1 到 m 次训练的进球情况，每个队员进球情况为连续的 1 和 0 的组合，不同队员用空格分隔

输出描述

射门能力从强到弱的队员编号，用空格分隔

用例输入4 5 11100 00111 10111 01111输出4 3 1 2说明

4个队员，射门训练5次，

队员3和4进球数均为4个，比队员1和2的3个更多，

队员3连续进球数最多一次为3个，而队员4最大为4，因此队员4射门能力强于队员3，

另外队员2比队员1先丢球，因此队员1射门能力强于队员2，

排序为4312

输入2 10 1011100111 1011101101输出2 1说明

2个队员，射门训练10次，

两个队员的进球总数均为7个，连续进球最多的均为3个，且第前两次丢球顺序均为第二次和第6次训练射门，

而队员2第三次丢球为第9次训练，队员2为第7次训练，

因此队员2的射门能力强于队员1,排序为21

题目解析

本题是一个自定义排序问题。按照题目描述要求的规则排序即可。

本题的难点主要在于队员的排序要素信息的收集，需要收集的排序要素，按照优先级分别为：

进球总数，即1的总数最多—次连续进球的个数，即最长连续1的长度射失索引列表，即0出现的索引位置队员编号

具体解析策略，请看代码实现。

JS算法源码 const rl = require("readline").createInterface({ input: process.stdin }); var iter = rl[Symbol.asyncIterator](); const readline = async () => (await iter.next()).value; class Player { constructor(number) { this.number = number; // 队员编号 this.totalGoal = 0; // 进球总数 this.maxConstantGoal = 0; // 最多—次连续进球的个数 this.missIdx = []; // 射失索引列表 } } void (async function () { const [n, m] = (await readline()).split(" ").map(Number); const shoots = (await readline()).split(" "); const players = []; for (let i = 0; i < n; i++) { const shoot = shoots[i]; const player = new Player(i + 1); // 记录某段连续进球数量 let constantOneCount = 0; for (let j = 0; j < m; j++) { if (shoot[j] == "1") { // 该队员进球总数+1 player.totalGoal++; // 该队员当前段连续进球数+1 player.maxConstantGoal = Math.max( player.maxConstantGoal, ++constantOneCount ); } else { // 失射会打断连续进球 constantOneCount = 0; // 统计失射索引 player.missIdx.push(j); } } players.push(player); } players.sort((a, b) => { // 进球总数更多的队员射门能力更强 if (a.totalGoal != b.totalGoal) { return b.totalGoal - a.totalGoal; } // 若进球总数—样多，则比较最多—次连续进球的个数，最多的队员能力更强 if (a.maxConstantGoal != b.maxConstantGoal) { return b.maxConstantGoal - a.maxConstantGoal; } // 若最多一次连续进球的个数一样多，则比较第一次射失的先后顺序，其中后射失的队员更强，若第一次射失顺序相同，则按继续比较第二次射失的顺序，后丢球的队员能力更强，依次类推 for (let i = 0; i < a.missIdx.length; i++) { if (a.missIdx[i] != b.missIdx[i]) { return b.missIdx[i] - a.missIdx[i]; } } // 若前3个规则排序后，还能力相等，则队员编号更小的能力更强 return a.number - b.number; }); const ans = players.map((player) => player.number).join(" "); console.log(ans); })();

Java算法源码 import java.util.ArrayList; import java.util.Scanner; import java.util.StringJoiner; public class Main { static class Player { int number; // 队员编号 int totalGoal; // 进球总数 int maxConstantGoal; // 最多—次连续进球的个数 ArrayList missIdx; // 射失索引列表 } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); ArrayList players = new ArrayList(); for (int i = 1; i { // 进球总数更多的队员射门能力更强 if (a.totalGoal != b.totalGoal) { return b.totalGoal - a.totalGoal; } // 若进球总数—样多，则比较最多—次连续进球的个数，最多的队员能力更强 if (a.maxConstantGoal != b.maxConstantGoal) { return b.maxConstantGoal - a.maxConstantGoal; } // 若最多一次连续进球的个数一样多，则比较第一次射失的先后顺序，其中后射失的队员更强，若第一次射失顺序相同，则按继续比较第二次射失的顺序，后丢球的队员能力更强，依次类推 for (int i = 0; i < a.missIdx.size(); i++) { int aMissIdx = a.missIdx.get(i); int bMissIdx = b.missIdx.get(i); if (aMissIdx != bMissIdx) { return bMissIdx - aMissIdx; } } // 若前3个规则排序后，还能力相等，则队员编号更小的能力更强 return a.number - b.number; }); for (Player player : players) { System.out.print(player.number + " "); } } }

Python算法源码 # 输入获取 n, m = map(int, input().split()) shoots = input().split() # 算法入口 def solution(): players = [] for i in range(n): shoot = shoots[i] totalGoal = 0 constantGoal = 0 # 记录某段连续进球数量 maxConstantGoal = 0 missIdx = [] for j in range(m): if shoot[j] == '1': # 该队员进球总数+1 totalGoal += 1 # 该队员当前段连续进球数+1 constantGoal += 1 maxConstantGoal = max(maxConstantGoal, constantGoal) else: # 失射会打断连续进球 constantGoal = 0 # 统计失射索引,这里录入-j, 当j越大, -j越小 missIdx.append(-j) # (进球总数, 最多—次连续进球的个数, 射失索引列表, 队员编号) players.append((-totalGoal, -maxConstantGoal, missIdx, i + 1)) # 这里sort函数默认升序，但是由于我们录入的-totalGoal，因此totalGoal越大, -totalGoal就越小, 此时明升暗降 players.sort() # x[3]是队员编号 return " ".join(map(lambda x: str(x[3]), players)) # 算法调用 print(solution())

C算法源码 #include #include #include #define MAX_M 1001 typedef struct { int number; // 队员编号 int totalGoal; // 进球总数 int maxConstantGoal; // 最多—次连续进球的个数 int missIdx[MAX_M]; // 射失索引列表 int missIdx_size; } Player; int cmp(const void *a, const void *b) { Player *A = (Player *) a; Player *B = (Player *) b; // 进球总数更多的队员射门能力更强 if (A->totalGoal != B->totalGoal) { return B->totalGoal - A->totalGoal; } // 若进球总数—样多，则比较最多—次连续进球的个数，最多的队员能力更强 if (A->maxConstantGoal != B->maxConstantGoal) { return B->maxConstantGoal - A->maxConstantGoal; } // 若最多一次连续进球的个数一样多，则比较第一次射失的先后顺序，其中后射失的队员更强，若第一次射失顺序相同，则按继续比较第二次射失的顺序，后丢球的队员能力更强，依次类推 for (int i = 0; i < A->missIdx_size; i++) { int aMissIdx = A->missIdx[i]; int bMissIdx = B->missIdx[i]; if (aMissIdx != bMissIdx) { return bMissIdx - aMissIdx; } } // 若前3个规则排序后，还能力相等，则队员编号更小的能力更强 return A->number - B->number; } int main() { int n, m; scanf("%d %d", &n, &m); Player players[n]; for (int i = 0; i < n; i++) { char shoot[MAX_M]; scanf("%s", shoot); Player player; player.number = i + 1; player.totalGoal = 0; player.maxConstantGoal = 0; player.missIdx_size = 0; // 记录某段连续进球数量 int constantGoal = 0; for (int j = 0; j < m; j++) { if (shoot[j] == '1') { // 该队员进球总数+1 player.totalGoal++; // 该队员当前段连续进球数+1 player.maxConstantGoal = (int) fmax(player.maxConstantGoal, ++constantGoal); } else { // 失射会打断连续进球 constantGoal = 0; // 统计失射索引 player.missIdx[player.missIdx_size++] = j; } } players[i] = player; } qsort(players, n, sizeof(players[0]), cmp); for (int i = 0; i < n; i++) { printf("%d ", players[i].number); } return 0; }

C++算法源码 #include using namespace std; class Player { public: int number{0}; // 队员编号 int totalGoal{0}; // 进球总数 int maxConstantGoal{0}; // 最多—次连续进球的个数 vector missIdx; // 射失索引列表 }; int main() { int n, m; cin >> n >> m; vector players(n); for (int i = 0; i < n; i++) { string shoot; cin >> shoot; players[i].number = i + 1; // 记录某段连续进球数量 int constantGoal = 0; for (int j = 0; j < m; j++) { if (shoot[j] == '1') { // 该队员进球总数+1 players[i].totalGoal++; // 该队员当前段连续进球数+1 players[i].maxConstantGoal = max(players[i].maxConstantGoal, ++constantGoal); } else { // 失射会打断连续进球 constantGoal = 0; // 统计失射索引 players[i].missIdx.emplace_back(j); } } } sort(players.begin(), players.end(), [](const Player &a, const Player &b) { // 进球总数更多的队员射门能力更强 if (a.totalGoal != b.totalGoal) { return a.totalGoal > b.totalGoal; } // 若进球总数—样多，则比较最多—次连续进球的个数，最多的队员能力更强 if (a.maxConstantGoal != b.maxConstantGoal) { return a.maxConstantGoal > b.maxConstantGoal; } // 若最多一次连续进球的个数一样多，则比较第一次射失的先后顺序，其中后射失的队员更强，若第一次射失顺序相同，则按继续比较第二次射失的顺序，后丢球的队员能力更强，依次类推 for (int i = 0; i < a.missIdx.size(); i++) { if (a.missIdx[i] != b.missIdx[i]) { return a.missIdx[i] > b.missIdx[i]; } } // 若前3个规则排序后，还能力相等，则队员编号更小的能力更强 return a.number < b.number; }); for (const auto &player: players) { cout

【本文地址】

华为校招机试

华为校招机试

今日新闻

推荐新闻