ACW4007.非零段划分

原题链接
image.png

思路

  • 模拟海水退潮的过程
  • 每遇到一个波峰，如果海水恰好在波峰的位置，那么岛屿的数量会增加1
  • 每遇到一个波谷，如果海水恰好在波谷的位置，那么岛屿的数量会减少1
  • 逐个遍历数组，记录海水在相应位置的变化（有可能多个波峰高度一致）
  • 模拟退潮过程，变化过程中一定会实现最大岛屿数量。

此题的关键在于掌握两点：

  1. 如何记录波峰波谷的数量（前后分别加上0），三个一组，从后往前扫（注意边界留空）

    2.  nums[0] = nums[n + 1] = 0;
    4.  n = unique(nums, nums + n + 2) - nums;
    5.  for (int i = 1; i < n; ++i) {
    6.      if (nums[i - 1] < nums[i] && nums[i] > nums[i + 1]) {
    7.          cnt[nums[i]] += 1;
    8.      } else if (nums[i - 1] > nums[i] && nums[i] < nums[i + 1]) {
    9.          cnt[nums[i]] -= 1;
    10.      }
    11.  }

  2. 如何进行去除相邻重复项（unique 和手动unique的方法都需要了解）（手动unique就是store_index指针）

    1. // cnt[i]表示水位如果在nums[i]高度，减少和增加的岛的数量
    2.  n = unique(nums, nums + n + 2) - nums;

    代码

    ```cpp

    include

    include

    include

    using namespace std;

const int N = 5e5 + 5; const int M = 1e5 + 5;

int main() { int n = 0; scanf(“%d”, &n); int nums[N], cnt[N]; memset(cnt, 0, sizeof(cnt)); for (int i = 1; i <= n; i++) { scanf(“%d”, &nums[i]); }

  1. nums[0] = nums[n + 1] = 0;
  3. // cnt[i]表示水位如果在nums[i]高度，减少和增加的岛的数量
  4. n = unique(nums, nums + n + 2) - nums;
  5. for (int i = 1; i < n; ++i) {
  6.     if (nums[i - 1] < nums[i] && nums[i] > nums[i + 1]) {
  7.         cnt[nums[i]] += 1;
  8.     } else if (nums[i - 1] > nums[i] && nums[i] < nums[i + 1]) {
  9.         cnt[nums[i]] -= 1;
  10.     }
  11. }
  13. // 逐个遍历，从高处往下降，模拟岛屿露出水面的过程
  14. int ans = 0, summ = 0;
  15. for (int i = M; i > 0; i--) {
  16.     summ += cnt[i];
  17.     ans = max(ans, summ);
  18. }
  20. printf("%d\n", ans);
  21. return 0;

} ```