2023‐08‐27 第 360 场周赛

距离原点最远的点

• 第一题初看有点难
• 想了一下 啪 很快啊 思路一下就打开了

class Solution {
public:
    int furthestDistanceFromOrigin(string moves) {
        int cntl = 0, cntr = 0, cnt_ = 0;
        
        for (auto c : moves) {
            if (c == 'L') cntl ++;
            
            if (c == 'R') cntr ++;
            
            if (c == '_') cnt_ ++;
        }
        
        return cnt_ + abs(cntl - cntr);
    }
};

找出美丽数的最小和

• 题目还好
• 罚了一次时
• res = accumulate(ans.begin(), ans.end(), 0); 这样写数据溢出了
• set 很少用

class Solution {
public:
    long long minimumPossibleSum(int n, int target) {
        // 最小和
        // 每次都选择最小的
        long long res = 0;
        
        set<int> num; // 记录最小数字对应的 另一个数字
        
        vector<int> ans; // 记录满足条件的最小数字
        
        int cnt = ans.size();
        
        int idx = 1;
        
        while (cnt < n) {
            if (num.count(idx)) idx ++;
            
            else {
                ans.emplace_back(idx);
                
                num.insert(target - idx);
                
                idx ++;
            }
            
            cnt = ans.size();
        }
        
        for (int i = 0; i < ans.size(); i ++) res += ans[i];
        
        return res;
    }
};

使子序列的和等于目标的最少操作次数

• 这题看着没什么难度
• 但是就是干瞪眼
• 想到了贪心 但是就是卡壳

class Solution {
public:
    int minOperations(vector<int> &nums, int target) {
        if (accumulate(nums.begin(), nums.end(), 0LL) < target)
            return -1;
        long long cnt[31]{};
        for (int x: nums)
            cnt[__builtin_ctz(x)]++;
        int ans = 0, i = 0;
        long long s = 0;
        while ((1LL << i) <= target) {
            s += cnt[i] << i;
            int mask = (1LL << ++i) - 1;
            if (s >= (target & mask))
                continue;
            ans++; // 一定要找更大的数操作
            for (; cnt[i] == 0; i++)
                ans++; // 还没找到，继续找更大的数
        }
        return ans;
    }
};