在牛牛面前放着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;
}
};
牛牛有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;
}
};
牛牛和牛妹在进行一场星球模拟游戏，游戏规则如下：
游戏地图内共有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;
}
};
本文地址：https://blog.csdn.net/Dragonlogin/article/details/107606120
如对本文有疑问， 点击进行留言回复！！
牛客编程巅峰赛S1第6场 - 黄金&钻石&王者题解
纵横字谜的答案 Crossword Answers, ACM/ICPC World Finals 1994, UVa232
HDU - 5880 Family View (AC自动机修改母串)
iOS14Beta3续航怎么样 iOS14Beta3续航能力介绍
iOS14Beta3稳定性怎么样 iOS14Beta3升级建议介绍
网友评论