比赛的冠亚季军

🕗 发布于 2025-01-21 15:48 算法笔试机试求职招聘华为OD E卷

比赛的冠亚季军

E 卷 100分题型

题目描述

有N（3 ≤ N < 10000）个运动员，他们的id为0到N-1,他们的实力由一组整数表示。他们之间进行比赛，需要决出冠亚军。比赛的规则是0号和1号比赛，2号和3号比赛，以此类推，每一轮，相邻的运动员进行比赛，获胜的进入下一轮；实力值大的获胜，实力值相等的情况，id小的情况下获胜；轮空的直接进入下一轮。

输入描述

输入一行N个数字代表N的运动员的实力值(0<=实力值<=10000000000)。

输出描述

输出冠亚季军的id，用空格隔开。

用例1

输入

2 3 4 5

输出

3 1 2

说明

第一轮比赛，

id为0实力值为2的运动员和id为1实力值为3的运动员比赛，1号胜出进入下一轮争夺冠亚军，

id为2的运动员和id为3的运动员比赛，3号胜出进入下一轮争夺冠亚军，

冠亚军比赛，3号胜1号，

故冠军为3号，亚军为1号，2号与0号，比赛进行季军的争夺，2号实力值为4，0号实力值2，故2号胜出，得季军。冠亚季军为3 1 2。

题解

思路：

模拟方法去处理
主要需要考虑奇数和偶数的情况就行

c++

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <sstream>

using namespace std;

// 运动员类
struct Sport {
    int id;          // 运动员的id
    long long strength; // 运动员的实力

    Sport(int id, long long strength) : id(id), strength(strength) {}
};

string getResult(vector<long long>& strengths);
void promote(vector<Sport>& sports, deque<vector<Sport>>& ans);

int main() {
    string input;
    getline(cin, input);

    stringstream ss(input);
    vector<long long> strengths;
    long long strength;

    while (ss >> strength) {
        strengths.push_back(strength);
    }

    cout << getResult(strengths) << endl;
    return 0;
}

string getResult(vector<long long>& strengths) {
    // ans只记录三个组，冠军组，亚军组，季军组
    deque<vector<Sport>> ans;

    // 将输入的实力值，转化为运动员集合
    vector<Sport> sports;
    for (int i = 0; i < strengths.size(); ++i) {
        sports.emplace_back(i, strengths[i]);
    }

    // 晋级赛
    promote(sports, ans);

    // 冠军组如果不是一个人，那么还需要取出冠军组继续进行晋级赛
    while (ans.front().size() > 1) {
        sports = ans.front();
        ans.pop_front();
        promote(sports, ans);
    }

    // 冠军
    int first = ans[0][0].id;

    // 亚军
    int second = ans[1][0].id;

    // 季军
    sort(ans[2].begin(), ans[2].end(), [](const Sport& a, const Sport& b) {
        return a.strength != b.strength ? a.strength > b.strength : a.id < b.id;
    });

    int third = ans[2][0].id;

    return to_string(first) + " " + to_string(second) + " " + to_string(third);
}

void promote(vector<Sport>& sports, deque<vector<Sport>>& ans) {
    // 记录获胜组
    vector<Sport> win;
    // 记录失败组
    vector<Sport> fail;

    for (int i = 1; i < sports.size(); i += 2) {
        Sport& major = sports[i];      // 序号大的运动员
        Sport& minor = sports[i - 1]; // 序号小的运动员

        if (major.strength > minor.strength) {
            win.push_back(major);
            fail.push_back(minor);
        } else {
            win.push_back(minor);
            fail.push_back(major);
        }
    }

    // 如果晋级赛中运动员个数是奇数个，那么最后一个运动员直接晋级
    if (sports.size() % 2 != 0) {
        win.push_back(sports.back());
    }

    // 依次头部压入失败组，获胜组，保证头部是获胜组
    ans.push_front(fail);
    ans.push_front(win);

    // 如果保留组个数超过3个，那么需要将超过部分的组去掉，因为这部分人已经无缘季军
    while (ans.size() > 3) {
        ans.pop_back();
    }
}

JAVA

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
  // 运动员类
  static class Sport {
    int id; // 运动员的id
    long strength; // 运动员的实力

    public Sport(int id, long strength) {
      this.id = id;
      this.strength = strength;
    }
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    long[] strengths = Arrays.stream(sc.nextLine().split(" ")).mapToLong(Long::parseLong).toArray();

    System.out.println(getResult(strengths));
  }

  public static String getResult(long[] strength) {
    // ans只记录三个组，冠军组，亚军组，季军组
    LinkedList<ArrayList<Sport>> ans = new LinkedList<>();

    // 将输入的实力值，转化为运动员集合
    ArrayList<Sport> sports = new ArrayList<>();
    for (int i = 0; i < strength.length; i++) sports.add(new Sport(i, strength[i]));

    // 晋级赛
    promote(sports, ans);

    // 冠军组如果不是一个人，那么还需要取出冠军组继续进行晋级赛
    while (ans.getFirst().size() > 1) {
      promote(ans.removeFirst(), ans);
    }

    // 冠军
    int first = ans.get(0).get(0).id;

    // 亚军
    int second = ans.get(1).get(0).id;

    // 季军
    ans.get(2)
        .sort(
            (a, b) ->
                a.strength != b.strength ? b.strength - a.strength > 0 ? 1 : -1 : a.id - b.id);
    
    int third = ans.get(2).get(0).id;
    return first + " " + second + " " + third;
  }

  public static void promote(ArrayList<Sport> sports, LinkedList<ArrayList<Sport>> ans) {
    // 记录获胜组
    ArrayList<Sport> win = new ArrayList<>();
    // 记录失败组
    ArrayList<Sport> fail = new ArrayList<>();

    for (int i = 1; i < sports.size(); i += 2) {
      // 序号大的运动员
      Sport major = sports.get(i);
      // 序号小的运动员
      Sport minor = sports.get(i - 1);

      if (major.strength > minor.strength) {
        win.add(major);
        fail.add(minor);
      } else {
        // 如果序号大的运动员的实力 <= 序号小的运动员，则序号小的运动员获胜
        win.add(minor);
        fail.add(major);
      }
    }

    // 如果晋级赛中运动员个数是奇数个，那么最后一个运动员直接晋级
    if (sports.size() % 2 != 0) {
      win.add(sports.get(sports.size() - 1));
    }

    // 依次头部压入失败组，获胜组，保证头部是获胜组
    ans.addFirst(fail);
    ans.addFirst(win);

    // 如果保留组个数超过3个，那么需要将超过部分的组去掉，因为这部分人已经无缘季军
    while (ans.size() > 3) ans.removeLast();
  }
}

Python

# 输入获取
tmp = list(map(int, input().split()))


class Sport:
    def __init__(self, idx, strength):
        self.idx = idx  # 运动员的id
        self.strength = strength    # 运动员的实力


# 将输入的实力值，转化为运动员集合
sports = []
for i in range(len(tmp)):
    sports.append(Sport(i, tmp[i]))


def promote(sports, ans):
    # 记录获胜组
    win = []
    # 记录失败组
    fail = []

    for i in range(1, len(sports), 2):
        # 序号大的运动员
        major = sports[i]
        # 序号小的运动员
        minor = sports[i-1]

        if major.strength > minor.strength:
            win.append(major)
            fail.append(minor)
        else:
            # 如果序号大的运动员的实力 <= 序号小的运动员，则序号小的运动员获胜
            win.append(minor)
            fail.append(major)

    # 如果晋级赛中运动员个数是奇数个，那么最后一个运动员直接晋级
    if len(sports) % 2 != 0:
        win.append(sports[-1])

    # 依次头部压入失败组，获胜组，保证头部是获胜组
    ans.insert(0, fail)
    ans.insert(0, win)

    # 如果保留组个数超过3个，那么需要将超过部分的组去掉，因为这部分人已经无缘季军
    while len(ans) > 3:
        ans.pop()


# 算法入口
def getResult():
    # ans只记录三个组，冠军组，亚军组，季军组
    ans = []

    # 晋级赛
    promote(sports, ans)

    # 冠军组如果不是一个人，那么还需要取出冠军组继续进行晋级赛
    while len(ans[0]) > 1:
        promote(ans.pop(0), ans)

    # 冠军
    first = ans[0][0].idx

    # 亚军
    second = ans[1][0].idx

    # 季军
    ans[2].sort(key=lambda x: (-x.strength, x.idx))
    third = ans[2][0].idx

    return f"{first} {second} {third}"


# 算法调用
print(getResult())import math

# 辗转相除法判断是否互质
def is_coprime(a, b):
    while b != 0:
        a, b = b, a % b
    return a == 1

# 判断是否相互互质
def are_coprime(a, b, c):
    return is_coprime(a, b) and is_coprime(a, c) and is_coprime(b, c)

def main():
    n = int(input())
    m = int(input())
    ans = []
    num = [0] * (m - n + 1)

    # 计算 n 到 m 之间每个数的平方
    for i in range(n, m + 1):
        num[i - n] = i * i

    s = set(num)  # 用集合去重

    # 寻找勾股数三元组
    for i in range(len(num)):
        for j in range(i + 1, len(num)):
            a_squared = num[i]
            b_squared = num[j]
            c_squared = a_squared + b_squared
            // 判断c^2是否是 [n,m]中整数的平方
            if c_squared not in s:
                continue
            c = int(math.sqrt(c_squared))
            // 判断是否互质
            if are_coprime(i + n, j + n, c):
                ans.append(f"{i + n} {j + n} {c}")

    # 输出结果
    if not ans:
        print("NA")
    else:
        for result in ans:
            print(result)

if __name__ == "__main__":
    main()

JavaScript

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", (line) => {
  const sports = line
    .split(" ")
    .map(Number)
    .map((val, idx) => new Sport(idx, val));

  console.log(getResult(sports));
});

function getResult(sports) {
  // ans只记录三个组，依次是：冠军组，亚军组，季军组
  const ans = [];

  // 晋级赛
  promote(sports, ans);

  // 冠军组如果不是一个人，那么还需要取出冠军组继续进行晋级赛
  while (ans[0].length > 1) {
    promote(ans.shift(), ans);
  }

  // 冠军
  const first = ans[0][0].id;
  // 亚军
  const second = ans[1][0].id;

  // 季军
  ans[2].sort((a, b) =>
    a.strength != b.strength ? b.strength - a.strength : a.id - b.id
  );
  const third = ans[2][0].id;

  return `${first} ${second} ${third}`;
}

function promote(sports, ans) {
  // 记录获胜组
  const win = [];
  // 记录失败组
  const fail = [];

  for (let i = 1; i < sports.length; i += 2) {
    // 序号大的运动员
    const major = sports[i];
    // 序号小的运动员
    const minor = sports[i - 1];

    if (major.strength > minor.strength) {
      win.push(major);
      fail.push(minor);
    } else {
      // 如果序号大的运动员的实力 <= 序号小的运动员，则序号小的运动员获胜
      win.push(minor);
      fail.push(major);
    }
  }

  // 如果晋级赛中运动员个数是奇数个，那么最后一个运动员直接晋级
  if (sports.length % 2 != 0) {
    win.push(sports.at(-1));
  }

  // 依次头部压入失败组，获胜组，保证头部是获胜组
  ans.unshift(fail);
  ans.unshift(win);

  // 如果保留组个数超过3个，那么需要将超过部分的组去掉，因为这部分人已经无缘季军
  while (ans.length > 3) ans.pop();
}

class Sport {
  constructor(id, strength) {
    this.id = id; // 运动员的id
    this.strength = strength; // 运动员的实力
  }
}

Go

package main

import (
"bufio"
"fmt"
"os"
"sort"
"strconv"
"strings"
)

// Sport 代表一个运动员，包含其 ID 和实力值
type Sport struct {
ID       int
Strength int64
}

// getResult 计算并返回冠军、亚军和季军的运动员 ID
func getResult(strengths []int64) string {
// ans 仅跟踪三个组：冠军组、亚军组、季军组
var ans [][]Sport

// 将输入的实力值转换为 Sport 对象
sports := make([]Sport, len(strengths))
for i, strength := range strengths {
sports[i] = Sport{ID: i, Strength: strength}
}

// 晋级赛
promote(sports, &ans)

// 继续晋级直到冠军组只剩下一个人
for len(ans[0]) > 1 {
firstGroup := ans[0]
ans = ans[1:] // 移除冠军组
promote(firstGroup, &ans)
}

// 冠军
first := ans[0][0].ID


// 亚军
second := ans[1][0].ID

// 对季军组按照实力降序排序，如果实力相同则按 ID 升序排序
sort.Slice(ans[2], func(i, j int) bool {
if ans[2][i].Strength != ans[2][j].Strength {
return ans[2][i].Strength > ans[2][j].Strength
}
return ans[2][i].ID < ans[2][j].ID
})
third := ans[2][0].ID

// 返回冠军、亚军和季军的 ID
return fmt.Sprintf("%d %d %d", first, second, third)
}

// promote 进行一轮晋级赛，将获胜组和失败组加入 ans
func promote(sports []Sport, ans *[][]Sport) {
// 获胜组
var win []Sport
// 失败组
var fail []Sport

// 按照比赛规则进行比较
for i := 1; i < len(sports); i += 2 {
major := sports[i]
minor := sports[i-1]

// 比较实力值
if major.Strength > minor.Strength {
win = append(win, major)
fail = append(fail, minor)
} else {
win = append(win, minor)
fail = append(fail, major)
}
}

// 处理奇数个运动员的情况
if len(sports)%2 != 0 {
win = append(win, sports[len(sports)-1])
}

// 将失败组和获胜组添加到 ans，确保获胜组在前
*ans = append([][]Sport{win, fail}, (*ans)...)


// 确保 ans 的大小不超过 3 个组
if len(*ans) > 3 {
*ans = (*ans)[:3]
}
}

func main() {
// 使用 bufio.Reader 来处理大输入
reader := bufio.NewReader(os.Stdin)
input, err := reader.ReadString('\n')
if err != nil {
fmt.Println("读取输入失败:", err)
return
}

// 解析输入
strengths := parseInput(input)

// 输出结果
fmt.Println(getResult(strengths))
}

// parseInput 将输入的字符串解析为实力值数组
func parseInput(input string) []int64 {
// 分割字符串
fields := strings.Fields(input)
strengths := make([]int64, len(fields))
for i, field := range fields {
val, err := strconv.ParseInt(field, 10, 64)
if err != nil {
fmt.Println("解析数字失败:", err)
return nil
}
strengths[i] = val
}
return strengths
}

原文地址：https://blog.csdn.net/qq_45776114/article/details/145271475

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Python+ tkinter实现小学整数乘法和除法竖式演算式
下一篇：Spring Boot整合WebSocket

C# LINQ（Language Integrated Query）详解
LINQ（语言集成查询）是C#和.NETFramework中的一项强大功能，它使开发人员可以在代码中使用类似SQL的查询语法，操作内存中的数据集合（如数组、列表、集合等），而不必依赖SQL语句。LIN
阅读更多2025-01-21
JAVA-IO模型的理解（BIO、NIO）
本文主要介绍了关于网络中的几种IO模型，以及每种模型的介绍和概念等，包括非阻塞模型中select，poll，epoll的介绍
阅读更多2025-01-21
Java-数据结构-二叉树(配图详解)
之前我们学习的顺序表(ArrayList)和链表(LinkedList)都是线性表也就都是线性的数据结构，而树则是一种非线性的数据结构，它由有限个结点组成一个具有层次关系的集合，之所以将它叫做&quo
阅读更多2025-01-21
从前端视角看设计模式之结构型模式篇
上篇介绍了设计模式之创建型模式，接下来介绍设计模式之结构型模式，这些模式关注对象之间的组合和关系，旨在解决如何构建灵活且可复用的类和对象结构
阅读更多2025-01-21
excel实用工具
excel工具
阅读更多2025-01-21
ThinkPHP 8的多对多关联
多对多关联属于比较复杂的关联，需要借助一个中间表实现，在模型中使用belongsToMany定义。在介绍ThinkPHP8的多对多语法之间，我们先来看一个例子，以加深对多对多关联的理解。比如我们开发一
阅读更多2025-01-21
【FPGA】MIPS 12条整数指令【1】
实现bgtz、bltz、jalr
阅读更多2025-01-21
STM32-CAN总线
CAN总线是由BOSCH公司开发的一种简洁易用、传输速度快、易扩展、可靠性高的串行通信总线。
阅读更多2025-01-21
【Golang 面试题】每日 3 题（三十八）
📚专栏简介：在这个专栏中，我将会分享Golang面试中常见的面试题给大家~
阅读更多2025-01-21
Acwing-基础算法课笔记之基础算法（二分）
然后将27与mid下标所在的数做比较，如果27<a[mid]，则将指针right更新，如果27>a[mid]，则将指针left更新，最终找到目标数。需要定义两个变量，一个left，一个ri
阅读更多2025-01-21

比赛的冠亚季军

比赛的冠亚季军

题目描述

输入描述

输出描述

用例1

输入

输出

说明

题解

c++

JAVA

Python

JavaScript

Go

相关文章