t3思路是对的，写的时候没写对
t4没想到二分，贪心想到了一点点，没写出来
滑铁卢，跌的最惨的一次了，已经很久没有只写出两题了。
DP这里得加强训练了。
5980. 将字符串拆分为若干长度为 k 的组
字符串 s 可以按下述步骤划分为若干长度为 k 的组：
- 第一组由字符串中的前 k 个字符组成，第二组由接下来的 k 个字符串组成，依此类推。每个字符都能够成为 某一个 组的一部分。
- 对于最后一组，如果字符串剩下的字符 不足 k 个，需使用字符 fill 来补全这一组字符。
注意，在去除最后一个组的填充字符 fill（如果存在的话）并按顺序连接所有的组后，所得到的字符串应该是 s 。
给你一个字符串 s ，以及每组的长度 k 和一个用于填充的字符 fill ，按上述步骤处理之后，返回一个字符串数组，该数组表示 s 分组后 每个组的组成情况 。
示例 1：
输入：s = “abcdefghi”, k = 3, fill = “x” 输出：[“abc”,”def”,”ghi”] 解释： 前 3 个字符是 “abc” ，形成第一组。 接下来 3 个字符是 “def” ，形成第二组。 最后 3 个字符是 “ghi” ，形成第三组。 由于所有组都可以由字符串中的字符完全填充，所以不需要使用填充字符。 因此，形成 3 组，分别是 “abc”、”def” 和 “ghi” 。
示例 2：
输入：s = “abcdefghij”, k = 3, fill = “x” 输出：[“abc”,”def”,”ghi”,”jxx”] 解释： 与前一个例子类似，形成前三组 “abc”、”def” 和 “ghi” 。 对于最后一组，字符串中仅剩下字符 ‘j’ 可以用。为了补全这一组，使用填充字符 ‘x’ 两次。 因此，形成 4 组，分别是 “abc”、”def”、”ghi” 和 “jxx” 。
提示：
- 1 <= s.length <= 100
- s 仅由小写英文字母组成
- 1 <= k <= 100
- fill 是一个小写英文字母
思路：
模拟
class Solution {public String[] divideString(String s, int k, char fill) {while (s.length() % k != 0) {s += fill;}String[] res = new String[s.length() / k];for (int i = 0; i < res.length; i++) {res[i] = s.substring(i * k, (i + 1) * k);}return res;}}
5194. 得到目标值的最少行动次数
你正在玩一个整数游戏。从整数 1 开始，期望得到整数 target 。
在一次行动中，你可以做下述两种操作之一：
- 递增，将当前整数的值加 1（即， x = x + 1）。
- 加倍，使当前整数的值翻倍（即，x = 2 * x）。
在整个游戏过程中，你可以使用 递增 操作 任意 次数。但是只能使用 加倍 操作 至多 maxDoubles 次。
给你两个整数 target 和 maxDoubles ，返回从 1 开始得到 _target _需要的最少行动次数。
示例 1：
输入：target = 5, maxDoubles = 0 输出：4 解释：一直递增 1 直到得到 target 。
示例 2：
输入：target = 19, maxDoubles = 2 输出：7 解释：最初，x = 1 。 递增 3 次，x = 4 。 加倍 1 次，x = 8 。 递增 1 次，x = 9 。 加倍 1 次，x = 18 。 递增 1 次，x = 19 。
示例 3：
输入：target = 10, maxDoubles = 4 输出：4 解释： 最初，x = 1 。 递增 1 次，x = 2 。 加倍 1 次，x = 4 。 递增 1 次，x = 5 。 加倍 1 次，x = 10 。
提示：
- 1 <= target <= 109
- 0 <= maxDoubles <= 100
思路：
直接按照最短路处理会超时。
考虑倒着处理，如果x是奇数，一定是加一得来的，x是偶数，能除以2就除以2，这样次数才最小。
class Solution {public int minMoves(int target, int m) {int cnt = 0;while (target > 1) {if (target % 2 == 0){if (m > 0) {m--;cnt++;target /= 2;} else {cnt += target - 1;break;}} else {cnt++;target--;}}return cnt;}}
5982. 解决智力问题
给你一个下标从 0 开始的二维整数数组 questions ，其中 questions[i] = [pointsi, brainpoweri] 。
这个数组表示一场考试里的一系列题目，你需要 按顺序 （也就是从问题 0 开始依次解决），针对每个问题选择 解决 或者 跳过 操作。解决问题 i 将让你 获得 pointsi 的分数，但是你将 无法 解决接下来的 brainpoweri 个问题（即只能跳过接下来的 brainpoweri 个问题）。如果你跳过问题 i ，你可以对下一个问题决定使用哪种操作。
- 比方说，给你 questions = [[3, 2], [4, 3], [4, 4], [2, 5]] ：
- 如果问题 0 被解决了， 那么你可以获得 3 分，但你不能解决问题 1 和 2 。
- 如果你跳过问题 0 ，且解决问题 1 ，你将获得 4 分但是不能解决问题 2 和 3 。
请你返回这场考试里你能获得的 最高 分数。
示例 1：
输入：questions = [[3,2],[4,3],[4,4],[2,5]] 输出：5 解释：解决问题 0 和 3 得到最高分。 - 解决问题 0 ：获得 3 分，但接下来 2 个问题都不能解决。 - 不能解决问题 1 和 2 - 解决问题 3 ：获得 2 分 总得分为：3 + 2 = 5 。没有别的办法获得 5 分或者多于 5 分。
示例 2：
输入：questions = [[1,1],[2,2],[3,3],[4,4],[5,5]] 输出：7 解释：解决问题 1 和 4 得到最高分。 - 跳过问题 0 - 解决问题 1 ：获得 2 分，但接下来 2 个问题都不能解决。 - 不能解决问题 2 和 3 - 解决问题 4 ：获得 5 分 总得分为：2 + 5 = 7 。没有别的办法获得 7 分或者多于 7 分。
提示：
- 1 <= questions.length <= 105
- questions[i].length == 2
- 1 <= pointsi, brainpoweri <= 105
思路：
方法1：倒序DP问题
状态表示：
表示
的最高得分
状态转移：若跳过当前题目：
若解决当前题目 
两者取Max
最终结果为
class Solution {public long mostPoints(int[][] q) {int n = q.length;long[] f = new long[n + 1];for (int i = n - 1; i >= 0; i--) {int j = q[i][1] + 1 + i;f[i] = f[i + 1];if (j >= n)f[i] = Math.max(f[i], q[i][0]);elsef[i] = Math.max(f[i], q[i][0] + f[j]);}return f[0];}}
方法2：正着做
状态表示：
表示
的最高得分
状态转移：若跳过当前题目
若解决当前题目，令
，有
最终结果为
class Solution {public long mostPoints(int[][] q) {int n = q.length;long[] f = new long[n + 1];for (int i = 0; i < n; i++) {f[i + 1] = Math.max(f[i + 1], f[i]);int j = q[i][1] + i + 1;if (j < n)f[j] = Math.max(f[j], f[i] + q[i][0]);elsef[n] = Math.max(f[n], f[i] + q[i][0]);}return f[n];}}
也可以用记忆化搜索
class Solution {long[] f = new long[100010];public long mostPoints(int[][] q) {return dp(q, 0);}long dp(int[][] q, int i) {if (i >= q.length)return 0;if (f[i] != 0) return f[i];f[i] = Math.max(dp(q, i + 1), dp(q, i + q[i][1] + 1) + q[i][0]);return f[i];}}
5983. 同时运行 N 台电脑的最长时间
你有 n 台电脑。给你整数 n 和一个下标从 0 开始的整数数组 batteries ，其中第 i 个电池可以让一台电脑 运行 batteries[i] 分钟。你想使用这些电池让 全部 n 台电脑 同时 运行。
一开始，你可以给每台电脑连接 至多一个电池 。然后在任意整数时刻，你都可以将一台电脑与它的电池断开连接，并连接另一个电池，你可以进行这个操作 任意次 。新连接的电池可以是一个全新的电池，也可以是别的电脑用过的电池。断开连接和连接新的电池不会花费任何时间。
注意，你不能给电池充电。
请你返回你可以让 n 台电脑同时运行的 最长 分钟数。
示例 1：
输入：n = 2, batteries = [3,3,3] 输出：4 解释： 一开始，将第一台电脑与电池 0 连接，第二台电脑与电池 1 连接。 2 分钟后，将第二台电脑与电池 1 断开连接，并连接电池 2 。注意，电池 0 还可以供电 1 分钟。 在第 3 分钟结尾，你需要将第一台电脑与电池 0 断开连接，然后连接电池 1 。 在第 4 分钟结尾，电池 1 也被耗尽，第一台电脑无法继续运行。 我们最多能同时让两台电脑同时运行 4 分钟，所以我们返回 4 。
示例 2：
输入：n = 2, batteries = [1,1,1,1] 输出：2 解释： 一开始，将第一台电脑与电池 0 连接，第二台电脑与电池 2 连接。 一分钟后，电池 0 和电池 2 同时耗尽，所以你需要将它们断开连接，并将电池 1 和第一台电脑连接，电池 3 和第二台电脑连接。 1 分钟后，电池 1 和电池 3 也耗尽了，所以两台电脑都无法继续运行。 我们最多能让两台电脑同时运行 2 分钟，所以我们返回 2 。
提示：
- 1 <= n <= batteries.length <= 105
- 1 <= batteries[i] <= 109
思路：
方法1：二分答案
如何确定当前电量mid能否满足要求？
如果当前电池电量超过mid，说明该电池只能供给一个电脑使用，多余的电被浪费了，假设这些电池能满足
个电脑供电
而当前电池电量小于等于mid，均能被完全使用。如何使用？每次均使用电量最多的
个，这样最终这些电池的电量要么为0，要么为1
只需要统计所有电池的可供电时间总和
，然后检查它们是否可以给 n 台电脑供电即可（即
）
class Solution {public long maxRunTime(int n, int[] b) {Arrays.sort(b);long all = 0;for (int x : b)all += x;long l = 0, r = all;while (l < r) {long mid = l + r + 1 >> 1;long cnt = 0, t = 0;for (int i = b.length - 1; i >= 0; i--) {if (b[i] > mid) {cnt += mid;t += b[i];} else break;}if (cnt + all - t < mid * n)r = mid - 1;else l = mid;}return l;}}
方法2：根据二分得出贪心的解法<br />不断缩小问题规模得以求解，对电池按电量排序<br />Start：计算总电量`S`，得出平均时间为<br />超过的电池被用于从始至终供应一台电脑<br />然后删掉该电池和电脑，继续从Start处开始处理<br />若当前最大容量电池的电量，说明该电量就是所有电脑平均最长时间，直接返回即可！
class Solution {public long maxRunTime(int n, int[] b) {int m = b.length;long sum = 0;Arrays.sort(b);for (int x :b)sum += x;long res = 0;for (int i = m - 1; i >= 0; i--) {if (b[i] > sum / n) {sum -= b[i];n--;} else {res = sum / n;break;}}return res;}}
若有收获，就点个赞吧
0 人点赞
