Luobuyu's Blog

0%

2106. 摘水果

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 2.7k 阅读时长 ≈ 2 分钟
很容易想到使用二分加前缀和解决，也可以使用滑动窗口更快地解决。

2106.摘水果

题目描述：

在 $x$ 轴上，有许多水果分布。给出一个二维整数数组fruits，其中 fruits[i] = [pos, amount]，表示共有amount个水果放在 pos 处。已经按照pos升序排列，每个pos都不相同。

另给出startPos和k，最初位于startPos。任何位置都可以向左或者向右走，每移动一个单位记为一步。总共可以走 $k$ 步。返回可以最多摘到的水果数量。

数据范围：

$1\le n\le 10^5;0\le startPos, pos \le 2\times 10^5;1\le amount\le 10^4;0\le k\le 2\times 10^5$

题解：

看 $k,n$ 的范围可知需要使用 $O(n)$ 或 $O(n\log(n))$ 的算法。

可以很容易想到使用前缀和方法，假设向左走了 $x$ ，向右走了 $y$ ，则 $2\times x + y = k$ ，枚举 $x$ 可以得到答案。同样也可以向右走 $x$ ，向左走 $y$ ，也满足同样的公式。需要注意的是因为 $pos$ 不连续，需要使用二分查找找到真实下标。 $lower\_bound$ 查找大于等于的， $-1$ 可以用来找左边界， $upper\_bound$ 查找大于的， $-1$ 可以用来找右边界。即

1
2
3
4
5
6
int get_sum(int left, int right)
{
    left = lower_bound(pos.begin(), pos.end(), left) - pos.begin() - 1;
    right = upper_bound(pos.begin(), pos.end(), right) - pos.begin() - 1;
    return sum[right] - sum[left];
}

也可以使用滑动窗口的方法：

首先假设窗口 $[l, r]$ 为最终遍历到的区间，则

  • $startPos < l$ 时，需要走 $r - startPos$ 步
  • $startPos > r$ 时，需要走 $start - l$ 步
  • $l\le startPos \le r$ 时，需要走 $r - l + \min(startPos - l, r - startPos)$ 步

可以使用公式 $r - l + \min(|startPos - l|, |r - startPos|)$ 来表示最少走的步数。同时发现当 $l$ 增大时，该值不会增加，只会减少或不变，是单调减的。因此可以通过滑动窗口维护。先for循环移动右窗口 $r$ ，当该值大于 $k$ 时while循环移动左窗口 $l$ 。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    vector<int> sum; // pos, sum
    vector<int> pos;

    int get_sum(int left, int right)
    {
        left = lower_bound(pos.begin(), pos.end(), left) - pos.begin() - 1;
        right = upper_bound(pos.begin(), pos.end(), right) - pos.begin() - 1;
        return sum[right] - sum[left];
    }
    int maxTotalFruits(vector<vector<int>> &fruits, int startPos, int k)
    {
        int n = fruits.size();
        sum.resize(n + 2);
        pos.resize(n + 2);
        pos[0] = -2e5 - 1;
        sum[0] = 0;
        for (int i = 1; i <= n; ++i)
        {
            pos[i] = fruits[i - 1][0];
            sum[i] = sum[i - 1] + fruits[i - 1][1];
        }
        pos[n + 1] = 2e5 + 1;
        sum[n + 1] = sum[n];
        int ans = 0, left, right;
        for (int x = 0; 2 * x <= k; ++x)
        {
            ans = max(ans, get_sum(startPos - x, startPos + k - 2 * x));
            ans = max(ans, get_sum(startPos - k + 2 * x, startPos + x));
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;

    int maxTotalFruits(vector<vector<int>> &fruits, int startPos, int k)
    {
        // [l, r]
        // r - l + min(|start - l|, |r - start|)
        int n = fruits.size();
        int l = 0, r = 0, sum = 0, ans = 0;
        for (; r < n; ++r)
        {
            while (l < r && ((fruits[r][0] - fruits[l][0] + min(fabs(startPos - fruits[l][0]), fabs(fruits[r][0] - startPos)))) > k)
            {
                sum -= fruits[l][1];
                l++;
            }
            sum += fruits[r][1];
            ans = max(ans, sum);
        }
        return ans;
    }
};