被迫隔离的周末，来个周赛解解乏
小编所在的社区因为疫情原因进行了 2 + 12 短期隔离，两天做了两遍鼻拭子和咽拭子的核酸检测，所幸都是阴性
人生第一次隔离，躺在床上刷完了好几部电影和综艺，实在没事做就来补了周赛的题
小伙伴们出行一定要戴口罩，注意疫情防护，共克时艰
本场周赛涉及到的知识点为：模拟、动态规划、逆向思维、二分答案、贪心
5980. 将字符串拆分为若干长度为 k 的组
给定一个字符串，将其按顺序分成若干个长度为 k 的组，不足 k 的补上字符x
题解
直接遍历模拟即可
// cpp
class Solution {
public:
vector<string> divideString(string s, int k, char fill) {
vector<string> vec;
string temp;
int cnt = 0;
for (auto& i: s) {
temp += i;
cnt++;
if (cnt == k) cnt = 0, vec.push_back(temp), temp = "";
}
while (cnt && cnt < k) cnt++, temp += fill;
if (cnt) vec.push_back(temp);
return vec;
}
};
5194. 得到目标值的最少行动次数
给定 tar ，你可以从 1 开始做两个操作
- 自增
- 加倍
你有最多 m 次加倍机会，请计算最少需要多少个操作可以得到tar
题解
尽可能大的数字加倍，这样操作数才少
逆向考虑，如果是奇数，直接自减，如果是偶数且有加倍机会，直接除以 2 ，如果没有机会了直接加上剩下的操作数即可
// cpp
class Solution {
public:
int minMoves(int tar, int m) {
int ans = 0;
while (tar > 1) {
if (tar % 2) tar--, ans++;
else {
if (m) m--, tar /= 2, ans++;
else {ans += tar - 1; break;}
}
}
return ans;
}
};
5982. 解决智力问题
给定 n 个题目，对于每个题目，可以选择做与不做
- 做的话有 a_{i} 的得分，但是没法做之后的 b_{i} 个题
- 不做的话可以继续做下面的题
请你计算最大的得分
数据规定1\leq n\leq 10^5
题解
动态规划，定义 dp_{i} 表示从 n - 1 做到第 i 题的最大得分
如果做第 i 题，那么可以由 i + b_{i} + 1 题转移过来
如果不做第 i 题，那么继承 i + 1 题的状态即可
答案即为 dp[0] ，时间复杂度为\mathcal{O}(n)
// cpp
class Solution {
public:
typedef long long LL;
LL mostPoints(vector<vector<int>>& q) {
int n = static_cast<int>(q.size());
vector<LL> dp(n + 1);
for (int i = n - 1; i >= 0; --i) {
dp[i] = max(dp[i + 1], dp[min(n, i + q[i][1] + 1)] + q[i][0]);
}
return dp[0];
}
};
5983. 同时运行 N 台电脑的最长时间
给定 n 个电脑和 n 个电池，每个电池的充电时长为a_{i} 每一个电池可以服役任意一个电脑，但是不能被充电
请计算这些电池能够同时给 n 个电脑充电的最长时间
数据规定1\leq n\leq 10^5,\ 1\leq a_{i}\leq 10^9
题解
如果 k 时间可以满足，那么 k 以下的时间也都可以，符合单调性，所以可以二分答案
考虑判定，本质上是判断电池的充电时长能否填满一个 k\times n 的矩阵，并且每一行不能有重复的电池
形式化的讲，设存在 n' 个电池，使得 a_{i} > k ，那么他们可以服役 n' 个电脑 k 时长
对于剩下的 a_{i} < k 的电池，只要 \sum{a_{i}} \geq (n - n')\cdot k ，我们就可以贪心地放电池，直到电池电量耗尽，从而保证所有电脑同时充电
因此只需要判定 \sum\limits_{i = 1}^{n}\min(a_{i},\ k)\geq n\cdot k 是否成立即可，时间复杂度为\mathcal{O}(n \log \sum\limits_{i = 1}^{n}{a_{i}})
// cpp
class Solution {
public:
typedef long long LL;
LL maxRunTime(int n, vector<int>& b) {
auto check = [&](LL mid) {
LL sum = 0;
for (auto& i: b) sum += min(mid, 1LL * i);
return n * mid <= sum;
};
LL l = 1, r = 0;
for (auto& i: b) r += i;
LL ans = 0;
while (l <= r) {
LL mid = (l + r) >> 1;
if (check(mid)) ans = mid, l = mid + 1;
else r = mid - 1;
}
return ans;
}
};
腾讯云开发者
