子数组，你让我拿什么爱你？

ACM算法日常

发布于 2021-12-20 10:12:22

32000

代码可运行

文章被收录于专栏：ACM算法日常ACM算法日常

运行总次数：0

代码可运行

周赛的时候被第二题卡了一下，自己之前做过子数组的问题，可以用单调栈优化，比赛的时候也往这方面想了

思维有点难度，老是有 bug，突然发现过了一千多人，这才感觉到不对劲，这才发现数据范围看错了，遂改为暴力，又要掉分了，死在子数组上...

涉及知识点：模拟、子数组、单调栈、双指针、前缀和、二分查找、离散化

5952. 环和杆

给定一个字符串形如 R3G2B1，表示杆子 3, 2, 1 上分别有 R, G, B 颜色的圈

解析这个字符串，返回杆子上集齐了 rgb 三种颜色的杆子数量

题解

直接按字符解析，用哈希表套集合处理即可

// cpp
class Solution {
public:
    int countPoints(string r) {
        unordered_map<int, set<int>> mp;
        for (int i = 0; i < r.size() - 1; i += 2) {
            int j = i + 1;
            if (!mp[r[j] - '0'].count(r[i])) mp[r[j] - '0'].insert(r[i]);
        }
        int ans = 0;
        for (auto& i: mp) {
            if (i.second.size() == 3) ans++;
        }
        return ans;
    }
};

5953. 子数组范围和

给定一个长度为 $n$ 的数组，返回所有子数组最大值与最小值差的和数据规定 $1\leq n\leq 10^3$

题解

这题比赛的时候想复杂了，直接爆炸数据范围不高，直接考虑 $\mathcal{O}(n^2)$ 的做法

可以固定左端点，枚举右端点，然后维护最大最小值即可

// cpp
class Solution {
public:
    long long subArrayRanges(vector<int>& nums) {
        typedef long long LL;
        int n = nums.size();
        LL ans = 0;
        for (int i = 0; i < n; ++i) {
            LL maxx = nums[i], minn = nums[i];
            for (int j = i + 1; j < n; ++j) {
                maxx = max(maxx, 1LL * nums[j]);
                minn = min(minn, 1LL * nums[j]);
                ans += maxx - minn;
            }
        }
        return ans;
    }
};

如果数据范围放大到 $1\leq n\leq 10^5$ ，需要考虑 $\mathcal{O}(n)$ 的做法

我们需要计算出每个元素 nums[i] 作为最大值、最小值所管辖的区间

以最大值为例，我们定义 dp[i] 表示到 i 为止最大值的和，我们需要用单调栈找到 i 左边第一个大于 nums[i] 的位置 j，然后可以状态转移方程 dp[i] = (j - i) * nums[i] + dp[j]，最小值同理

// cpp
class Solution {
public:
    long long subArrayRanges(vector<int>& nums) {
        typedef long long LL;
        int n = nums.size();
        vector<LL> maxx(n + 1), minn(n + 1);
        vector<int> lse(n + 1, 0), lge(n + 1, 0);
        stack<int> stk;
        for (int i = n; i >= 1; --i) {
            while (!stk.empty() && nums[stk.top() - 1] < nums[i - 1]) {
                lge[stk.top()] = i;
                stk.pop();
            }
            stk.push(i);
        }
        while (!stk.empty()) stk.pop();
        for (int i = n; i >= 1; --i) {
            while (!stk.empty() && nums[stk.top() - 1] > nums[i - 1]) {
                lse[stk.top()] = i;
                stk.pop();
            }
            stk.push(i);
        }
        LL ans = 0;
        for (int i = 1; i <= n; ++i) {
            //cout << i << ' ' << lge[i] << ' ' << lse[i] << endl;
            int j = lge[i];
            maxx[i] = 1LL * (i - j) * nums[i - 1] + maxx[j];
            j = lse[i];
            minn[i] = 1LL * (i - j) * nums[i - 1] + minn[j];
            ans += maxx[i] - minn[i];
        }
        return ans;
    }
};

5954. 给植物浇水 II

数轴上分布了 $n$ 个植物， $A,\ B$ 从两头开始给植物浇水，每个人水桶的容量分别为 $CA,\ CB$

如果植物所需要的水量超过当前水桶的量，他们需要补水，计算浇灌结束所有植物的时候，他们补水的次数

数据规定 $1\leq n\leq 10^5$

题解

两个指针从数组两头扫描，模拟浇灌的过程，时间复杂度 $\mathcal{O}(n)$

// cpp
class Solution {
public:
    int minimumRefill(vector<int>& p, int ca, int cb) {
        int n = p.size();
        int i = 0, j = n - 1, a = ca, b = cb, ans = 0;
        while (i <= j) {
            if (i == j) {
                if (a == b) {
                    if (a < p[i]) a = ca, ans++;
                    a -= p[i++];
                }
                else if (a < b) {
                    if (b < p[j]) b = cb, ans++;
                    b -= p[j--];
                }
                else {
                    if (a < p[i]) a = ca, ans++;
                    a -= p[i++];
                }
            }
            else {
                if (a < p[i]) ans++, a = ca;
                a -= p[i++];
                if (b < p[j]) ans++, b = cb;
                b -= p[j--];
            }
        }
        return ans;
    }
};

5955. 摘水果

给定一个坐标轴，上面分布了 $n$ 个水果，每个水果有自己的坐标 $p_{i}$ 和价值 $f_{i}$ 你位于 $st$ ，每次移动一单位耗费一点体力值，你一共有 $k$ 体力，计算可以获得的最大水果价值数据规定 $1\leq n\leq 10^5,\ 1\leq p_{i},\ st,\ k\leq 2\cdot 10^5,\ 1\leq f_{i}\leq 10^4$

题解

考虑从 $st$ 出发，向右走 $x$ ，那么向左走 $y = \frac{(k - x)}{2}$ ，轨迹为 $[st - y, st + x]$ ，我们只要计算该区间的最大价值即可考虑从 $st$ 出发，向左走 $x$ ，那么向右走 $y = \frac{(k - x)}{2}$ ，轨迹为 $[st - x, st + y]$ ，我们只要计算该区间的最大价值即可预处理前缀和，在数轴不那么大的情况下，我们可以直接计算整个数轴的前缀和，时间复杂度 $\mathcal{{O}(k)}$

// cpp
class Solution {
public:
    int maxTotalFruits(vector<vector<int>>& f, int st, int k) {
        int n = f.size();
        int max_r = (*(max_element(f.begin(), f.end(), [&](const vector<int>& a, const vector<int>& b) {
            return a[0] < b[0];
        })))[0] + 1;
        //cout << max_r << endl;
        vector<int> sum(max_r + 1);
        for (int i = 0; i < n; ++i) {
            sum[f[i][0] + 1] += f[i][1];
        }
        for (int i = 1; i <= max_r; ++i) {
            sum[i] += sum[i - 1];
        }
        st++;
        int ans = 0;
        for (int x = k; x >= 0; --x) {
            int y = (k - x) / 2;
            int L1 = max(1, st - y), R1 = min(max_r, st + x);
            int L2 = max(1, st - x), R2 = min(max_r, st + y);
            if (L1 > R1 && L2 > R2) continue;
            if (L1 <= R1) ans = max(ans, sum[R1] - sum[L1 - 1]);
            if (L2 <= R2) ans = max(ans, sum[R2] - sum[L2 - 1]);
        }
        return ans;
    }
};

如果数轴特别大，需要离散化记录前缀和，否则时间和空间都会爆炸，时间复杂度为 $\mathcal{O}(k\cdot \log n)$

// cpp
class Solution {
public:
    int maxTotalFruits(vector<vector<int>>& f, int st, int k) {
        int n = f.size();
        vector<int> sum;
        sum.push_back(0);
        for (int i = 1; i <= n; ++i) {
            sum.push_back(f[i - 1][1] + sum[i - 1]);
        }
        vector<int> pos;
        for (auto& i: f) pos.push_back(i[0]);
        int ans = 0;
        for (int x = k; x >= 0; --x) {
            int y = (k - x) / 2;
            int L = st - y, R = st + x;
            auto l = lower_bound(pos.begin(), pos.end(), L) - pos.begin();
            auto r = upper_bound(pos.begin(), pos.end(), R) - pos.begin();
            ans = max(ans, sum[r] - sum[l]);
            L = st - x, R = st + y;
            l = lower_bound(pos.begin(), pos.end(), L) - pos.begin();
            r = upper_bound(pos.begin(), pos.end(), R) - pos.begin();
            ans = max(ans, sum[r] - sum[l]);
        }
        return ans;
    }
};