机关网站建设 方案,查做外贸客户的网站,wordpress主题时尚科技,jsp网站开发实训题目 有N(3N10000)个运动员#xff0c;他们的id为0到N-1,他们的实力由一组整数表示。他们之间进行比赛#xff0c;需要决出冠亚军。比赛的规则是0号和1号比赛#xff0c;2号和3号比赛#xff0c;以此类推#xff0c;每一轮#xff0c;相邻的运动员进行比赛#…题目 有N(3N10000)个运动员他们的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号实力值为40号实力值2故2号胜出得季军。 冠亚季军为3 1 2。 思路 每轮相邻的运动员分入一组比赛每轮结束后数组的长度由len变为(len1)/2加一的原因为轮空的直接进入下一轮。具体来讲 假设len为偶数8那么每轮len的变化过程为8421长度为2时争夺冠亚长度为1时得到冠军长度为4时可以得到4强季军为4强中非冠亚的较大值。 假设len为基数9那么每轮len的变化过程为95321长度为2时争夺冠亚长度为1时得到冠军长度为3时3个运动员中减去冠亚就得到季军。 所以当数组长度降低为3或4时最终的冠亚季军都在这个数组中可以先保存数组的值。然后继续下一轮当进行到最后一轮时len1得到了冠军再反推回来就可以分别得到亚军和季军。 考虑到实力分值范围最大值为10000000000超过了Integer所以实力分值应该用long表示 题解
package hwod;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;public class Competition2 {public static void main(String[] args) {Scanner sc new Scanner(System.in);long[] nums Arrays.stream(sc.nextLine().split( )).mapToLong(Long::parseLong).toArray();int[] res competition(nums);for (int i 0; i res.length; i) {if (i ! 0) System.out.print( );System.out.print(res[i]);}}private static int[] competition(long[] nums) {int[] res new int[3];//存储最终的冠亚季军idint[] indexs new int[nums.length];//记录每个人的id每轮淘汰时淘汰id即可for (int i 0; i nums.length; i) {indexs[i] i;}ListInteger lst4 new ArrayList();//存储4强while (indexs.length 1) {if (indexs.length 4 || indexs.length 3) {lst4 Arrays.stream(indexs).boxed().collect(Collectors.toList());}int[] newIndexs new int[(indexs.length 1) / 2]; //每轮淘汰一半的人数for (int i 0; i indexs.length; i 2) {if (i 1 indexs.length nums[indexs[i]] nums[indexs[i 1]]) {newIndexs[i / 2] indexs[i 1];} else {newIndexs[i / 2] indexs[i];}}if (newIndexs.length 1) {//得出冠军res[0] newIndexs[0];//得到亚军此时indexs长度必为2排除冠军就是亚军了res[1] indexs[0] res[0] ? indexs[1] : indexs[0];}indexs newIndexs;}Integer[] lst4new lst4.stream().filter(x - x ! res[0] x ! res[1]).toArray(Integer[]::new);//从4强里排除冠亚军如果剩余1个那么那一个就是季军如果剩余2个那么其中的较大值是季军。if (lst4new.length 1 || lst4new[0] lst4new[1]) {res[2] lst4new[0];} else {res[2] lst4new[1];}return res;}
}
使用indexs来记录运动员的编号可能不太直观可以考虑直接使用自定义对象来进行排序。如下
package hwod;import java.util.*;
import java.util.stream.Collectors;public class Competition2 {private static ListCPlayer wins new ArrayList();public static void main(String[] args) {Scanner sc new Scanner(System.in);int[] nums Arrays.stream(sc.nextLine().split( )).mapToInt(Integer::parseInt).toArray();int[] res competition(nums);for (int i 0; i res.length; i) {if (i ! 0) System.out.print( );System.out.print(res[i]);}}private static int[] competition(int[] nums) {int[] res new int[3];for (int i 0; i nums.length; i) {wins.add(new CPlayer(i, nums[i]));}ListCPlayer lst4new ArrayList();while (wins.size() 2) {if (wins.size()4||wins.size()3) {lst4 wins;}ListCPlayer tmpList new ArrayList();for (int i 0; i wins.size(); i 2) {//0,说明按照排序规则i该排在i1后面即i1晋级if (i 1 wins.size() wins.get(i).compareTo(wins.get(i 1)) 0) {tmpList.add(wins.get(i 1));} else {tmpList.add(wins.get(i));}}wins tmpList;}//最后剩下的wins一定是两个长度产生冠亚军ListCPlayer loser lst4.stream().filter(x - !wins.contains(x)).collect(Collectors.toList());Collections.sort(wins);Collections.sort(loser);res[0] wins.get(0).getId();res[1] wins.get(1).getId();res[2] loser.get(0).getId();return res;}class CPlayer implements ComparableCPlayer {private int id;private long score;public int getId() {return id;}public void setId(int id) {this.id id;}public long getScore() {return score;}public void setScore(long score) {this.score score;}public CPlayer(int id, long score) {this.id id;this.score score;}Overridepublic int compareTo(CPlayer o) {if (this.score o.score) return this.id - o.id;return Long.compare(o.score, this.score);}
}
推荐
如果你对本系列的其他题目感兴趣可以参考华为OD机试真题及题解JAVA查看当前专栏更新的所有题目。
