第360场Leetcode周赛 | Crystal’s Blog

type

Post

status

Published

date

Aug 27, 2023

slug

第360场Leetcode周赛

summary

C-贪心

题解

如果数组之和sum<target，则输出-1。

因为所有数字都可以分解成1，可以组合成1~sum之间的任何数字。

考虑target的二进制形式。例如7（111）。从低位到高位遍历，依次判断每一位是否能在数组中无需分解就能合成。

以下的数都用第几位来表示，例如4是第2位。如果target的第i位不能合成，那么就分解数组中第一个比它大的数，用第j位表示。第j位可以分解出第j-1位，第j-2位…两个第i位。1个第i位用于合成，其他累加到数组中去。

注意：累加函数 accumulate（）里的0必须是0LL，否则会爆int。（血的教训！）

💡

1、为什么target需要从低往高遍历，而不是从高往低？

回答：如果将小的数留在最后，那么遇到分解情况时需要花费更多的步数。

c++代码


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
class Solution
{
public:
    int minOperations(vector<int> &nums, int target)
    {
        ll n = nums.size();
        ll sum = accumulate(nums.begin(), nums.end(), 0LL);
        if (sum < target)
        {
            return -1;
        }
        map<ll, ll> count; // 统计每个数字的个数
        for (auto x : nums)
        {
            count[x]++;
        }
        ll ans = 0;
        ll lower_bit = 1;
        while (target)
        {
            if (target & 1)
            {
                ll x = lower_bit; // 判断数组中比x小的数能不能合成x
                for (ll i = x; i >= 1; i /= 2)
                {
                    if (count[i] > 0)
                    {
                        x -= (min(x / i, count[i])) * i;
                    }
                }
                if (x > 0)
                {
                    ll x = lower_bit, y = 0; // y为第一个比x大的数
                    for (ll i = x * 2; i <= pow(2, 30); i *= 2)
                    {
                        if (count[i] > 0)
                        {
                            y = i;
                            break;
                        }
                    }
                    ll t = log2(y / x);
                    ans += t;
                    count[y]--;
                    // 分解出的其他数加到count里去
                    for (ll i = x; i <= y / 2; i *= 2)
                    {
                        count[i]++;
                    }
                }
                else
                { // 合成成功
                    ll x = lower_bit;
                    for (ll i = x; i >= 1; i /= 2)
                    {
                        if (count[i] > 0)
                        {
                            ll t = min(x / i, count[i]);
                            x -= t * i;
                            count[i] -= t;
                        }
                    }
                }
            }
            lower_bit *= 2;
            target >>= 1;
        }
        return ans;
    }
};