牛客编程巅峰赛S1第6场 - 黄金&钻石&王者

A 牛牛爱奇数

解题思路
这道题有两种解法，第一种是贪心的思路，我们每一次肯定优先将一些大的偶数先变小，让它与那些小的偶数相等之后，再统一变成奇数，而每一次选出当前最大的一个偶数当然要使用大根堆。

参考代码

import java.util.*;


public class Solution {
    /**
     * 返回一个数，代表让这些数都变成奇数的最少的操作次数
     * @param n int整型 代表一共有多少数
     * @param a int整型一维数组 代表n个数字的值
     * @return int整型
     */
    public int solve (int n, int[] a) {
        // write code here
        PriorityQueue<Integer> q = new PriorityQueue<Integer>(new Comparator<Integer>() {

            @Override
            public int compare(Integer o1, Integer o2) {
                // TODO Auto-generated method stub
                return o2 - o1;
            }
        });

        Set<Integer> set = new HashSet<Integer>();
        for(int i=0; i<n; i++){
            if(a[i] % 2 == 0 && !set.contains(a[i])){
                set.add(a[i]);
                q.add(a[i]);
            }
        }

        int cnt = 0;
        while(!q.isEmpty()){
            int tmp = q.poll();

            tmp /= 2;
            cnt += 1;

            if(!set.contains(tmp) && tmp % 2 == 0){
                set.add(tmp);
                q.add(tmp);
            }
        }

        return cnt;
    }
}

第二种解法就是我们知道，在该转化中所有出现的偶数都要做除2的操作，由于要统计最少的步数，故这里我们让每一种偶数都只除一次2，这样最终就可以统计出所需的最少的步数。

import java.util.*;


public class Solution {
    /**
     * 返回一个数，代表让这些数都变成奇数的最少的操作次数
     * @param n int整型 代表一共有多少数
     * @param a int整型一维数组 代表n个数字的值
     * @return int整型
     */
    public int solve (int n, int[] a) {
        // write code here
        Set<Integer> set = new HashSet<Integer>();

        int cnt = 0;
        for(int i=0; i<n; i++){

            while(a[i] % 2 == 0){
                if(!set.contains(a[i])){
                    cnt += 1;
                }
                set.add(a[i]);
                a[i] /= 2;
            }
        }

        return cnt;
    }
}

B 牛牛摆放花

解题思路
这道题是一个很经典的贪心，思路就是将最大的数字放到中间，然后依次将第2大和第3大的放到两边，第4大的接在第二大的后面，第5大的接在第3大的后面，按照这样的顺序最后得到的就是一个相邻差值最小的序列。

解题思路

import java.util.*;


public class Solution {
    /**
     * 返回按照这些花排成一个圆的序列中最小的“丑陋度”
     * @param n int整型 花的数量
     * @param array int整型一维数组 花的高度数组
     * @return int整型
     */
    public int solve (int n, int[] a) {
        // write code here
        int ans = 0;

        if(n == 1) return 0;

        Arrays.sort(a);

        for(int i=0; i+2<n; i++){
            ans = Math.max(ans, a[i + 2] - a[i]);
        }
        ans = Math.max(ans, a[n-1] - a[n - 2]);
        ans = Math.max(ans, a[1] - a[0]); 

        return ans;
    }
}

C 星球游戏

解题思路
这道题是图论问题中最短路的一个经典的应用，由于 $n$ 和 $m$ 的值都很大，所以想到的最短路算法肯定有spfa或者是Dijkstra, 这里写两种方法都是可以的，这里我写的是Dijkstra算法，具体的思路就是建立一个虚拟源点，它到牛牛的所有星球的距离都为0，然后从这个虚拟源点出发求到其它各个点的最短路，最终遍历一下牛妹的所有星球，找到一个最短的返回就好了。

牛客编程巅峰赛S1第6场 - 黄金&钻石&王者

A 牛牛爱奇数

B 牛牛摆放花

C 星球游戏

全站热榜