欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-14 10:06:31
...

牛牛爱奇数

链接: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),显然超时。于是,发现可以加个中间件,也就是虚拟初始结点,便可以解决问题。如图
牛客编程巅峰赛S1第6场 - 黄金&钻石&王者题解

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

最短路算法总结

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

代码

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)
相关标签: 牛客编程巅峰赛