首页 > 作文

算法题解 – 牛客编程巅峰赛S1第6场 – 黄金&钻石&王者组

更新时间:2023-04-08 20:54:26 阅读: 评论:0

A. 牛牛爱奇数

题目描述

在牛牛面前放着 n 个数,这些数字既有奇数也有偶数,只不过牛牛对奇数情有独钟,他特别想让这些数都变成奇数。

现在牛牛获得了一种能力,他可以执行一种操作:每次选中一个偶数,然后把这些数中与该数相等的数都除以 2,例如现在有一个数组为 [2, 2, 3],那么牛牛可以执行一次操作,使得这个数组变为 [1, 1, 3]。

牛牛现在想知道,对于任意的 n 个数,他最少需要操作多少次,使得这些数都变成奇数?

备注:

1 ≤ n ≤ 10^6,代表一个有多少数字a1, a2, a3 ... an(1 ≤ ai ≤ 10^9)代表数字的大小

示例1

输入

3,[2,2,3]

输出

1

说明

只需做一次操作,会将其中的偶数2都变成1,满足了所有的数都是奇数的要求。

示例2

输入

3,[1,3,7]

输出

0

说明

不需要做任何操作,因为所有的数原本就是奇数。

解法:大顶堆 + 哈希集合

思路分析

每次可以让所有相同的偶数变成一半,问最少操作次数。

一次操作所有相同数,显然要使用哈希集合进行去重。

而要使得操作次数最少,必然对偶数从大到小进行操作,这样才可以避免对某个偶数进行重复的操作。

想要从大到小操作,显然使用大顶堆保存偶数。每次从堆顶取一个数字进行操作,若得到的新的数字是偶数并且未在哈希集合中出现过,就把它再加入大顶堆中。

时间复杂度:O(max(n, logm))。这里的 m 是最大的偶数。遍历一遍数字需要 O(n),把偶数全变成奇数需要 O(logm)。

空间复杂度:O(n)。

代码实现

public int solve (int n, int[] a) {  Set<Integer> t = new HashSet();  int ans = 0;  for(int i: a)    if((i & 1) == 0) t.add(i);  Queue<Integer> q = new PriorityQueue<Integer>((x,y) -> y - x);  q.addAll(t);  while(!q.isEmpty()) {    int num = q.poll()11月14日是什么节日 >> 1;    ans++;    if((num & 1) == 0 && !t.contains(num)) q.add(num);  }  return ans;}

B. 牛牛摆放花

题目描述

牛牛有 n 朵需要摆放的花,但是每朵花呢,高度都不一样,牛牛不喜欢相邻的花高度相差太多,这样会影响美感。

所以牛牛提出了一个“丑陋度”的概念,“丑陋度”意思为在一个摆放序列中,相邻花高度差的最大值。而且牛牛是一个完美主义者,所以他希望:

1.将这些花摆成乏味首尾相接的圆形

2.为了美观,他希望摆放的花“丑陋度”最小

程序应返回:按照这些花排成一个圆的顺序,输出在多个摆放花的序列中,最小的“丑陋度”。

备注:

第一个参数为一个整数 n(2 ≤ n ≤ 10^5),代表花的数量。第二个参数为包含 a1, a2, a3 ... an(1 ≤ ai ≤ 10^9) 的数组,代表每朵花的高度。

示例1

输入

5,[2,1,1,3,2]

输出

1

说明

可以摆成 1 2 3 2 1这样的序列,最小的“丑陋度”为1

示例2

输入

3,[30,10,20]

输出

20

说明

可以摆成10 30 20这样的序列,最小的“丑陋度”为20

解法:排序

思路分析

如果不考虑首尾相接的话,要想丑陋度最小,显然摆放序列为升序/降序。

现在要求首尾相接,因此首尾的高度差也要小一些,显然 V 型 序列或者 ^ 型 序列满足要求。

故而进行排序,升序/降序都可以。这里以升序为例,高度差 = arr[i] – arr[i – 2]。首尾高度差 = arr[1] – arr[0]。

时间复杂度:O(nlogn)。

空间复杂度:O(1)。

代码实现

public int solve (int n, int[] array) {  Arrays.sort(array);  int ans = array[1] - array[0];  for(int i = 2; i < n; i++)     ans = Math.max(ans, array[i] - array[i - 2]);  return ans;}

C. 星球游戏

题目描述

牛牛和牛妹在进行一场星球模拟游戏,游戏规则如下:

游戏地图内共有 n 个星球,共有 m 条隧道连接这些星球。每条隧道都是双向的,每两个星球间不一定只有一条隧道。现在牛牛占领了这 n 个星球中的 p 个星球,牛妹占领了这 n 个星球中的 q 的星球(每个星球最多只能被一个人占领)。现袋的组词在牛牛想知道他占领的 p 个星球中任意一个星球,到牛妹占领的 q 个星球中任意一个星球,这两个星球的最短距离是多少。

备注:

2 ≤ n ≤ 1e5, 0 ≤ m ≤ 2e5, 1 ≤ p ≤ 1e5, 1 ≤ q ≤ 1e5, p + q ≤ n, min(p, q) ≤ 10, 1 ≤ wi ≤ 1e4  相关参数意义如下  niuniu 牛牛占领的p个星球的编号  niumei 牛妹占领的q个星球的编号  path  m条隧道,每条隧道有三个数分别是ui,vi,wi。ui,vi分别是隧道的两边星球的编号,wi是它们之间的距离  nn int整型 星球个数n

示例1

输入

[1],[3,4],[[1,2,7],[2,3,6],[3,4,2],[1,3,11],[2,4,3]],4

输出

10

说明

距离最近的牛牛星和牛妹星是 1 和 4,他们之间的距离为 10

示例2

输入

[1],[2],[],2

输出

-1

说明

所有的牛牛星和牛妹星都不联通,故输出 -1

解法:dijkstra算法

思路分析

显然这题是单源最短路问题,直接使用 dijkstra 算法可解。

有人可能要问了:“汪汪,牛牛不是占领了 p 个星球吗,怎么会是单源最短路问题?”

注意到题目中说的是 p 个星球中任意一个,所以法力无边的本汪创造了一个超级星球 X,从 X 出发可以瞬移到牛牛的 p 个星球,因此本题就等价于问从星球 X 出发,到牛妹占领的星球中最近距离是多少。就这样轻轻松松地变成一个单源最短路问题了。

本汪默认聪明博学的小伙伴们都会 dijkstra 算法,在这就不多赘述了。(才不是因为我懒)

如果有小伙伴对 dijkstra 算法还有疑问,可以在下方留言,有需求的话本汪就专门出一期 dijkstra 算法的博客。

代码实现

public class Solution {    /** * * @param niuniu int整型一维数组 牛牛占领的p个星球的编号 * @param niumei int整型一维数组 牛妹占领的q个星球的编号 * @param path int整型二维数组 m条隧道,每条隧道有三个数分别显性遗传是ui,vi,wi。ui,vi分别是隧道的两边星球的编号,wi是它们之间的距离 * @param nn int整型 星球个数n * @return int整型 */    final int INF = 10001;    public int Length (int[] niuniu, int[] niumei, int[][] path, int nn) {    List<Pair>[] edges = new List[nn + 1];    int[] dis = new int[nn + 1];    Arrays.fill(dis, INF);    boolean[] vis = new boolean[nn + 1];    for(int i = 0; i <= nn; i++) edges[i] = new ArrayList();    for(int[] edge: path) {    edges[edge[0]].add(new Pair(edge[2],edge[1]));    edges[edge[1]].add(new Pair(edge[2],edge[0]));    }    Queue<Pair> q = new PriorityQueue<Pair>((a, b) -> a.d - b.d);    for(int u: niuniu) {    dis[u] = 0;    q.add(new Pair(0, u));    }    while(!q.isEmpty()) {    Pair p = q.poll();    if(vis[p.v]) continue;    vis[p.v] = true;    for(Pair e: edges[p.v]) {    if(dis[e.v] > dis[p.v] + e.d) {    dis[e.v] = dis[p.v] + e.d;    q.offer(new Pair(dis[e.v],e.v));    }    }    }    int ans = INF;    for(int u: ni诗歌的表现手法umei) ans = Math.min(ans, dis[u]);    return ans == INF ? -1 : ans;    }}class Pair{int d; //距离int v; //另一个顶点public Pair(int d, int v) {this.d = d;this.v = v;}}

写在最后

「牛客编程巅峰赛系列题解」也写了八期了,每篇文章都要耗费大量的时间进行撰写、排版、纠错。但对小伙伴们的帮助却不大,本汪 也是产生了一丢丢的挫败感。
暂不打算继续更新这个系列的文章了。
新的计划是更新「解题方法系列」的文章。第一期的标题我都想好了:【遇到「最值问题」无脑动态规划?二分法考虑一下呗】。预计一周内更新。
如果小伙伴想了解其他方面的知识,可以在下方评论区留言哦。本汪 会视情况决定是否新开这个系列。

本文地址:https://blog.csdn.net/weixin_43971405/article/details/107593861

本文发布于:2023-04-08 20:54:25,感谢您对本站的认可!

本文链接:https://www.wtabcd.cn/fanwen/zuowen/b4b8200a520944fe551f3b015aec6584.html

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

本文word下载地址:算法题解 – 牛客编程巅峰赛S1第6场 – 黄金&钻石&王者组.doc

本文 PDF 下载地址:算法题解 – 牛客编程巅峰赛S1第6场 – 黄金&钻石&王者组.pdf

标签:星球   牛牛   偶数   奇数
相关文章
留言与评论(共有 0 条评论)
   
验证码:
Copyright ©2019-2022 Comsenz Inc.Powered by © 专利检索| 网站地图