ChuChu愛游泳 的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： YummyBerry

觀看題解前請先好好想過題目，觀看完題解後也想想為什麼這樣寫能AC，如果你因此寫出比我效率更好的程式就更棒了٩(◦`꒳´◦)۶。

這題我原本想用分治法解(max(左邊最大值, 右邊最大值, 左牆+右牆體積))。

但發現如果測資長下面這樣就會出事。

1 1 1 1 5 5 1 1 1 1

觀察後發現如果用雙指標指向頭跟尾可以解決。

因為只要是包含在頭尾內的牆 AND 牆比頭跟尾都還要矮，就代表這個牆不可能形成更大的體積。(可以自行想想看為什麼，上面的題目的示意圖應該有幫助)

以下是作法：

  1. 從小的那個開始往後or往前找比自己更大的值(target)。

  2. 找到後把指標改成(target)，同時算體積。

  3. 重複1, 2步驟直到 l >= r。

以下是程式碼：

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define sakura ios_base::sync_with_stdio(false), cin.tie(0);
using namespace std;


signed main()
{
    sakura int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++)
    {
        cin >> nums[i];
    }

    int max = 0, l = 0, r = n - 1;
    while (l < r)
    {
        // cout << l  << " " << r << "\n";
        int temp = (r - l) * min(nums[l], nums[r]);
        if (max < temp)
            max = temp;

        int cnt;
        if (nums[r] < nums[l])
        {
            cnt = r - 1;
            while (nums[r] >= nums[cnt])
            {
                cnt--;
                if (r == l)
                    break;
            }
            r = cnt;
        }
        else
        {
            cnt = l + 1;
            while (nums[l] >= nums[cnt])
            {
                cnt++;
                if (r == l)
                    break;
            }
            l = cnt;
        }
    }
    cout << max;

    return 0;
}

评论

目前没有评论。