牛客编程巅峰赛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 星球游戏

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

参考代码

import java.util.*;

class Node implements Comparable<Node>{

    int t;
    long val;

    public Node(int t, long val){
        this.t = t;
        this.val = val;
    }

    @Override
    public int compareTo(Node o) {
        // TODO Auto-generated method stub
        return Long.compare(val, o.val);
    }
}


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整型
     */
    int N = 100010, M = 600010, max = 0x3f3f3f3f;
    int[] h = new int[N];
    int[] dist = new int[N];
    boolean[] st = new boolean[N];
    int[] e = new int[M];
    int[] ne = new int[M];
    int[] w = new int[M];
    int idx;

    void add(int a, int b, int c){
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx ++;
    }

    void dijkstra(){
        Arrays.fill(dist, max);
        dist[0] = 0;

        PriorityQueue<Node> q = new PriorityQueue<Node>();
        q.add(new Node(0, 0));

        while(!q.isEmpty()){
            Node cur = q.poll();

            int t = cur.t;
            if(st[t]) continue;
            st[t] = true;

            for(int i=h[t]; i!=-1; i=ne[i]){
                int j = e[i];

                if(dist[j] > dist[t] + w[i]){
                    dist[j] = dist[t] + w[i];
                    q.add(new Node(j, dist[j]));
                }
            }
        }
    }

    public int Length (int[] a, int[] b, int[][] e, int nn) {
        // write code here
        Arrays.fill(h, -1);

        for(int i=0; i<a.length; i++){
            add(0, a[i], 0);
            add(a[i], 0, 0);
        }

        for(int[] cur : e){
            int u = cur[0];
            int v = cur[1];
            int w = cur[2];

            add(v, u, w);
            add(u, v, w);
        }

        dijkstra();

        int res = max;
        for(int i=0; i<b.length; i++) res = Math.min(res, dist[b[i]]);

        if(res == max) return -1;
        else return res;
    }
}

这次比赛打的非常不好，写一句话鼓励一下自己吧QWQ: