lc.5980 将字符串拆分为若干长度为 k 的组

字符串 s 可以按下述步骤划分为若干长度为 k 的组：
第一组由字符串中的前 k 个字符组成，第二组由接下来的 k 个字符串组成，依此类推。每个字符都能够成为 某一个 组的一部分。
对于最后一组，如果字符串剩下的字符 不足 k 个，需使用字符 fill 来补全这一组字符。
注意，在去除最后一个组的填充字符 fill（如果存在的话）并按顺序连接所有的组后，所得到的字符串应该是 s 。
给你一个字符串 s ，以及每组的长度 k 和一个用于填充的字符 fill ，按上述步骤处理之后，返回一个字符串数组，该数组表示 s 分组后 每个组的组成情况 。

• ac

class Solution {
public:
    vector<string> divideString(string s, int k, char fill) {
        vector<string> ans;
        string tmp;
        int cnt = 0;
        for(int i = 0 ; i < s.size() ; i ++){
            if(cnt < k){
                tmp += s[i];
            }
            else{
                cnt = 0;
                ans.emplace_back(tmp);
                tmp.clear();
                tmp += s[i];
            }
            cnt ++;
        }
        if(!tmp.empty()){
            for(int i = tmp.size() ; i < k ; i ++){
                tmp += fill;
            }
            ans.emplace_back(tmp);
        }
        return ans;
    }
};

lc.5194 得到目标值的最少行动次数

你正在玩一个整数游戏。从整数 1 开始，期望得到整数 target 。
在一次行动中，你可以做下述两种操作之一：
递增，将当前整数的值加 1（即， x = x + 1）。
加倍，使当前整数的值翻倍（即，x = 2 * x）。

在整个游戏过程中，你可以使用 递增 操作 任意 次数。但是只能使用 加倍 操作 至多 maxDoubles 次。
给你两个整数 target 和 maxDoubles ，返回从 1 开始得到 target 需要的最少行动次数。

• 超时

class Solution {
public:
    void cal(int& target , int& maxDoubles , int& cnt){
        if(target == 1) return;
        if(target % 2 == 0 && maxDoubles != 0){
            target = target / 2;
            cnt ++;
            maxDoubles --;
            cal(target, maxDoubles, cnt);
        }
        else{
            target = target - 1;
            cnt ++;
            cal(target, maxDoubles, cnt);
        }
    }
    int minMoves(int target, int maxDoubles) {
        int cnt = 0;
        cal(target, maxDoubles, cnt);
        return cnt;
    }
};

• ac

class Solution {
public:
    int minMoves(int target, int maxDoubles) {
        int cnt = 0;
        for(int i = 0 ; i < maxDoubles ; i ++){
            if(target <= 2) break;
            if(target % 2 != 0) cnt ++;
            target = target / 2 ;
            cnt ++;
        }
        cnt += target - 1;
        return cnt;

    }
};

lc.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 。

请你返回这场考试里你能获得的 最高 分数。

• wrong ans

class Solution {
public:
    void search(int& n, long long& ans, vector<vector<int>>& questions, int tmp){
        if(n >= questions.size()) return;
        tmp += questions[n][0];
        if(tmp > ans) ans = tmp;
        for(int i = 0 ; i + n + 1 < questions.size() ; i ++){
            n += 1 + i + questions[n][1];
            search(n , ans, questions, tmp);
        }
    }
    long long mostPoints(vector<vector<int>>& questions) {
        long long ans = 0;
        for(int i = 0 ; i < questions.size() ; i ++){
            int n = i;
            int tmp = 0;
            search(n , ans, questions, tmp);
        }
        return ans;
    }
};

• dp

class Solution {
    long long f[200005];
public:
    long long mostPoints(vector<vector<int>>& q) {
        for(int i=q.size()-1;i>=0;i--) {
            f[i]=max(f[i+1],q[i][0]+f[i+q[i][1]+1]);
        }
        return f[0];
    }
};

lc.5983 同时运行 N 台电脑的最长时间

你有 n 台电脑。给你整数 n 和一个下标从 0 开始的整数数组 batteries ，其中第 i 个电池可以让一台电脑 运行 batteries[i] 分钟。你想使用这些电池让 全部 n 台电脑 同时 运行。
一开始，你可以给每台电脑连接 至多一个电池 。然后在任意整数时刻，你都可以将一台电脑与它的电池断开连接，并连接另一个电池，你可以进行这个操作 任意次 。新连接的电池可以是一个全新的电池，也可以是别的电脑用过的电池。断开连接和连接新的电池不会花费任何时间。
注意，你不能给电池充电。
请你返回你可以让 n 台电脑同时运行的 最长 分钟数。

• 二分

class Solution {
public:
    long long maxRunTime(int n, vector<int>& b) {
        sort(b.begin(),b.end());
        long long ret=0;
        long long l=0,r=1ll * 1e9 * 100000;
        while (l<=r) {
            long long mid=(l+r) / 2;
            long long sum=0;
            for(int i=0;i<b.size();i++) sum+=min(1ll * b[i],mid);
            if (sum>=n * mid) {
                l=mid+1;
                ret=mid;
            }
            else r=mid-1;
        }
        return ret;
    }
};