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

牛牛爱奇数

链接：https://ac.nowcoder.com/acm/contest/6629/A
来源：牛客网

题目描述

在牛牛面前放着n个数，这些数字既有奇数也有偶数，只不过牛牛对奇数情有独钟，他特别想让这些数都变成奇数。
现在牛牛获得了一种能力，他可以执行一种操作：每次选中一个偶数，然后把这些数中与该数相等的数都除以2，例如现在有一个数组为[2,2,3][2,2,3]，那么牛牛可以执行一次操作，使得这个数组变为[1,1,3][1,1,3]。
牛牛现在想知道，对于任意的n个数，他最少需要操作多少次，使得这些数都变成奇数？

题目分析

数据量为1000000，根据数据量推出此题最坏的时间复杂度为O(nlogn).
于是想，这题可以排序后再做吗？发现可以按照从大到小排序，每次选取一个最大的偶数 v，然后让数组中所有的 v / 2,那么问题来了，是真的要改变v的值为v / 2吗？

假设我们需要改变v = v/2， 那么做法就是找到所有的v然后进行改变，显然很麻烦，还可能会超时。
其实，一般需要改变数组值的做法都可以转化为虚拟改值，增加一个中间件，以间接达到改变值的目的。

所以，这里可以增加一个map<int,int>来统计每个偶数出现的次数，然后按照从偶数大的来依次/2处理。先选大的用到了贪心思想。

代码

class Solution {
public:
    /**
     * 返回一个数，代表让这些数都变成奇数的最少的操作次数
     * @param n int整型 代表一共有多少数
     * @param a int整型vector 代表n个数字的值
     * @return int整型
     */
    
    int solve(int n, vector<int>& a) {
        // write code here
        map<int,int> mp; // map 自动按照 key 拍好序
        for (int it : a) {
            if (it % 2 == 0) {
                mp[it]++;
            }
        }
        
        int ret = 0;
        auto it = mp.rbegin();
        // 按照 key 从大到小遍历
        for (; it != mp.rend(); it ++) {
            cout << it->first << endl;
            int fir = it->first / 2;
            ret ++ ;
            if (fir % 2 == 0) {
                mp[fir] += it->second;
            }
        }
        return ret;
    }
};

• 时间复杂度：O(n)

---

牛牛摆放花

链接：https://ac.nowcoder.com/acm/contest/6629/B
来源：牛客网

题目描述

牛牛有n朵需要摆放的花，但是每朵花呢，高度都不一样，牛牛不喜欢相邻的花高度相差太多，这样会影响美感。
所以牛牛提出了一个“丑陋度”的概念，“丑陋度”意思为在一个摆放序列中，相邻花高度差的最大值。而且牛牛是一个完美主义者，所以他希望:
1.将这些花摆成首尾相接的圆形
2.为了美观，他希望摆放的花“丑陋度”最小
程序应返回：按照这些花排成一个圆的顺序，输出在多个摆放花的序列中，最小的“丑陋度”。

题目分析

数据量为100000，所以考虑时间复杂度为O(nlogn)
根据样例可以容易看出，贪心可以解决，将数据从大到小排序，然后按照将数据从中间往左右两个方向进行组织排列(这里用deque数据结构比较好)，拍好之后，在找相邻间的最大值即可。

代码

class Solution {
public:
    /**
     * ​返回按照这些花排成一个圆的序列中最小的“丑陋度”
     * @param n int整型 花的数量
     * @param array int整型vector 花的高度数组
     * @return int整型
     */
    int solve(int n, vector<int>& array) {
        // write code here
        sort(array.begin(), array.end(), greater<int>());
        deque<int> q;
        for (int i = 0; i < n; ++ i) {
            int t = array[i];
            if (i&1) {
                q.push_back(t);
            }else {
                q.push_front(t);
            }            
             
        }
        int ret = INT_MIN;
        for (int i = 1; i < n; ++ i) {
            ret = max(ret, abs(q[i] - q[i - 1]));
        }
        return ret;
    }
};

• 时间复杂度：O(nlogn)

---

星球游戏

链接：https://ac.nowcoder.com/acm/contest/6629/C
来源：牛客网

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

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

题目分析

数据量：结点为100000，边数为200000
乍一分析，题目要求一个点集合到另一个点集合的最短距离。懵了，根据最短距离的算法，发现可以用floyd算法（O(n^3），显然超时。于是，发现可以加个中间件，也就是虚拟初始结点，便可以解决问题。如图

p，q分别为两个点集合，加个虚拟初始结点vir，并且让vir到q集合中每个点的权值为0，于是问题就变成了了单元最短路径问题，从起点vir跑一遍spfa算法，然后再遍历一遍p集合，找到最短路径即可。

最短路算法总结

代码

const int N = 100010;
typedef pair<int,int> PII;
vector<PII> g[N];
int dist[N];
bool st[N];
int n;
class Solution {
public:
    /**
     *
     * @param niuniu int整型vector 牛牛占领的p个星球的编号
     * @param niumei int整型vector 牛妹占领的q个星球的编号
     * @param path int整型vector<vector<>> m条隧道，每条隧道有三个数分别是ui,vi,wi。ui,vi分别是隧道的两边星球的编号，wi是它们之间的距离
     * @param nn int整型 星球个数n
     * @return int整型
     */
    void spfa() {
        memset(dist, 0x3f, sizeof dist);
        dist[0] = 0;
        queue<int> q({0});
        st[0] = true;

        while (q.size()) {
            auto u = q.front();
            q.pop();
            st[u] = false;

            for (auto& e : g[u]) {
                int v = e.first, w = e.second;
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    if (!st[v]) {
                        q.push(v);
                        st[v] = true;
                    }
                }
            }
        }

       
    }
    int Length(vector<int>& niuniu, vector<int>& niumei, vector<vector<int> >& path, int nn) {
        // write code here
        n = nn;
        for (auto &e : path) {
            int x = e[0], y = e[1], z = e[2];
            g[x].push_back({y, z});
            g[y].push_back({x, z});
            
        }
        for(int x : niumei) {
            g[0].push_back({x, 0});
        }
        spfa();
        int ret = 0x3f3f3f3f;
        for (int x : niuniu){
            ret = min(ret, dist[x]);
        }
        return ret == 0x3f3f3f3f ? -1 : ret;
    }
};

• 时间复杂度：O(m)