评论

• 
  

  0

  

  YummyBerry  于2023年6月4日 13:52评论

  題解

  觀看題解前請先好好想過題目，觀看完題解後也想想為什麼這樣寫能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;
  }