牛牛爱奇数
链接: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 ++) { 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)