两种思路:
① 奇、偶身高分别一个栈,然后交替出栈入队,最后剩下的全入队。注意,因为每个人对左右都能产生共献,所以要人数多的先入队,比如【偶,奇,偶】
用到了O(N)的额外空间
#include <bits/stdc++.h> using namespace std; const size_t MAX_N = 100002; uint a[MAX_N]; int main() { int n; cin >> n; stack<uint> odd, even; for(int i = 0; i < n; i++) { cin >> a[i]; if(a[i] & 1) odd.push(a[i]); else even.push(a[i]); } vector<uint> order; while(odd.size() && even.size()) { if(odd.size() > even.size()) { order.push_back(odd.top()); order.push_back(even.top()); } else { order.push_back(even.top()); order.push_back(odd.top()); } odd.pop(); even.pop(); } while(odd.size()) { order.push_back(odd.top()); odd.pop(); } while(even.size()) { order.push_back(even.top()); even.pop(); } for(int i = 0; i < order.size(); i++) cout << order[i] << (i == order.size() - 1 ? "\n" : " "); return 0; }
② 基本思路同上,但是奇偶各一个链表,少的往多的里面插,变成经典的合并链表,O(1)空间复杂度
代码略
基本思路:找到所有模式串的下标,保存到一个数组,然后按左右下标间隔k,遍历下标数组,计算最短长度
#include <bits/stdc++.h> using namespace std; const string TARGET = "mihoyo"; const size_t TARGET_LEN = TARGET.size(); int main() { int n, k; cin >> n >> k; string str; cin >> str; vector<size_t> mihoyoPosition; size_t p = -1; // 全部出现位置 while((p = str.find(TARGET, p + 1)) != string::npos) mihoyoPosition.push_back(p); // 不足k个 if(mihoyoPosition.size() < k) { cout << "-1\n"; return 0; } // 找结果 pair<int, int> answer; size_t minLength = UINT_MAX; int l = 0, r = k - 1; while(r < mihoyoPosition.size()) { size_t len = mihoyoPosition[r] - mihoyoPosition[l]; if(len < minLength) { minLength = len; answer = {mihoyoPosition[l], mihoyoPosition[r] + TARGET_LEN - 1}; } ++l, ++r; } cout << answer.first << ' ' << answer.second << '\n'; return 0; }
计算每一个元素,严格大于前一个数需要翻倍的次数
设是的下一个数
对于,可以解出
再考虑对于每一个数被翻倍后,后面的数理应同等地一起进行翻倍(或者说,需要先翻完前一个数翻倍的次数,再去做“为了大于前一个数而进行的翻倍”)
因此将每一个数需要的存到一个数组里,然后计算前缀和,最后再求和
仔细考虑特殊情况:
① ,即已经满足了严格递增,解出的会是0或负数,负数实际有意义,说明前缀和累加到自己的时候,可以少翻几次。但是前缀和始终应当非负。
② 与恰好差了2的幂次倍数,为了“严格递增”,需要加一
代码:
#include <bits/stdc++.h> using namespace std; typedef long long LL; const size_t MAX_N = 100002; int a[MAX_N], mark[MAX_N]; /* 记录每个数的k(大于前一个数需要翻倍的次数) */ int main() { size_t n; cin >> n; for(int i = 0; i < n; i++) cin >> a[i]; for(int i = 1; i < n; i++) { int k = int(ceil(log2(a[i - 1]) - log2(a[i]))); // 如果前后两个正好差2^t倍,多乘一个2(为了严格递增) double t = log2(a[i - 1] * 1.0 / a[i]); mark[i] = abs(ceil(t) - floor(t)) <= 1E-6 ? k + 1 : k; } LL ans = 0, sum = 0; for(int i = 1; i < n; i++) { sum = sum + mark[i]; if(sum < 0) sum = 0; ans += sum; } cout << ans << '\n'; return 0; }#笔试题目##米哈游笔试##米哈游秋招##米哈游23秋招笔试心得体会#