正文索引 [隐藏]

传送门

t1 存在连续三个奇数的数组

签到题，直接O(n²)遍历就能过。

class Solution {
public:
    bool threeConsecutiveOdds(vector<int>& arr) {
        const int n = arr.size();
        
        if(n < 3) 
            return false;
            
        for(int i = 2; i < n; i++)
        {
            int cnt = 0;
            for(int j = i-2; j <= i; j++)
            {
                if(arr[j] % 2 != 0 || arr[j] == 1) 
                    cnt++;

                if(cnt == 3)
                    return true;
            }
        }

        return false;
    }
};

t2 使数组中所有元素相等的最小操作数

找规律贪心的题。给你一个数组，数组中每个元素i的值等于2*i+1(就是一个奇数序列)。每次操作可以选一个元素++再选一个元素–，问最少用多少次操作可以把整个序列的值化等。

不难发现，对于一个有序奇数列，最简单的方法就是以中位元素为分界线，右边的元素每次操作-1，左边的元素每次操作+1。根据这个策略分类讨论直接计算次数就行了。

class Solution {
public:
    int minOperations(int n) {
        if(n % 2)
        {
            int ans = 0;
            int mid = n / 2;
            
            for(int i = 1; i <= mid; i++)
                ans += i * 2;
            
            return ans;
        }
        else
        {
            int ans = 0;
            int mid = n / 2;
            
            for(int i = 1; i <= mid; i++)
                ans += (i * 2) - 1;
            
            return ans;
        }
    }
};

t3 两球之间的磁力

题目要求是求“最大的最小磁力”，那么可以考虑枚举磁力f。

思考一下不难得知，最小的磁力一定来自于相邻的两个球。所以，对于每个磁力f，确定它符合“任意两个相邻的球的距离都≥f”的条件，统计出所有f中最大的那一个即可。

考虑到数据范围，直接枚举绝对会超时，所以用二分，枚举关键字是距离，初始状态下left=0,right=INF=1e9。

class Solution {
public:
    const int INF = 1e9 + 5;

    bool check(int f, vector<int>& p, int m, int n) {
        int lastPos = p[0];m--;
        
        for(int i = 1; i < n && m > 0; i++)
        {
            if(p[i] - lastPos >= f)
            {
                m--;
                lastPos = p[i];
            }
        }

        return m <= 0;
    }

    int maxDistance(vector<int>& position, int m) {
        sort(position.begin(), position.end());
        int left = 0, right = INF, ans = 0;
        const int n = position.size();

        while(left <= right)
        {
            int mid = left + (right - left) / 2;
            
            if(check(mid, position, m, n))
            {
                ans = max(ans, mid);
                left = mid + 1;
            }
            else right = mid - 1;
        }

        return ans;
    }
};

赛时遇到这题懵了好一阵，下来学习到了这类“最小的最大/最大的最小”一般都是二分答案的题，也算是背个板子吧。

小秀一下双百~

t4 吃掉 N 个橘子的最少天数

这是一道hard，又是一道dp。

每次操作有三种选择

  1. 吃一个橘子
  2. 如果剩下的橘子能被2整除，吃½的橘子。
  3. 如果剩下的橘子能被三整除，吃⅔的橘子

那么就存在很明显的状态转移关系，但是这题跟经典的dp不太一样，因为它的n范围足足有2e9，直接裸来肯定是要爆空间的。

这道题的状态分布十分离散(我也不知道为什么…参考坑神的实况视频原话)，所以用map来贪空间，每次用find查询状态，可以节省很多空间。

关于这三种操作，显然可以得知，在能够进行操作2、3的情况下绝对不会优先进行操作1，这是一个贪心的思想，那么操作1就与2、3绑定起来了，转移时也只需要考虑操作2、3。

状态转移方程是：

dp[n] = min(dfs(n/2) + 1 + (n % 2), dfs(n/3) + 1 + (n % 3));

方程中dfs(n/2)很好理解，调用n/2这个状态的值，”+1″是算上“吃一半苹果”这个操作本身占用的一个次数，(n%2)是计算“通过操作1将橘子数调整到能被2整除”这个操作消耗的次数，如果它本身能被2整除这个数就是0，反之为1。方程的后半截结构同上。

有了方程这题的代码就十分简单了。

class Solution {
public:
    map<int, int> dp;

    int ans(int n)
    {
        if(n == 1) return 1;
        if(n == 2 || n == 3) return 2;

        if(dp.find(n) != dp.end()) return dp[n];

        dp[n] = min(ans(n/2) + 1 + (n % 2), ans(n/3) + 1 + (n % 3));

        return dp[n];
    }

    int minDays(int n) {
        dp.clear();
        return ans(n);
    }
};