编程题（没做出来，2020.09.05）

题意：输入一个序列，求蓄水之和

例子

输入 0 1 0 2 1 0 1 3 2 1 2

输出 6

思路：贪心，双指针

#include<bits/stdc++.h>
#define MAXVAL 100005
using namespace std;


int calArea(vector<int>& arr)
{
    int n = arr.size();
    if(n<3) return 0;  // 由于要蓄水，最少三根柱子。所以边界为3
    int ans = 0;

    int l, r;  // 初始化左右指针为0，1
    for (l = 0, r = l+1; r<n && arr[r]>=arr[l]; ++l, ++r);
    // 首先找【大，小】模式作为开端，

    r++;   // 三个数为单位搜寻
    while(r<n)
    {
      if (arr[l]<arr[r]) // A情况 ，只有当左指针小于右指针的时候，计算中间的面积
      {

        int base = min(arr[l], arr[r]);
        for (int i = l+1; i < r; ++i) if(base >= arr[i]) ans += (base-arr[i]);
        l = r;
        r += 2;
      }
      else ++r;  // B情况，搜寻大于左指针的柱子
    }

    if(r == n)  //如果从循环A情况跳出，说明还有剩下的面积没考虑，计算中间面积
    {
      //计算面积[l,r]
      r--;
      int base = min(arr[l],arr[r]);
      for (int i = l+1; i < r; ++i) if(base >= arr[i])  ans += (base-arr[i]); 
    }

  return ans; 
}


int main(int argc, char const *argv[])
{
    int n;
    cin>>n;
    vector<int> v(n);
    for (int i = 0; i < n; ++i) cin>>v[i];

    cout<<calArea(v);
    return 0;
}

事后诸葛亮

别着急写代码，我当时应该是没有正确理解题目意思，（由于有个图，我一直以为两个柱子相等也可以装水，这让我很懵），所以毫无思路。编码本身并不复杂，重要的是思路！！！ 在纸上想好怎么处理，写一个算法梗概，编码是自然而然的事情。没有想好解题思路，只会让自己更加紧张，从而“死锁”。

编码心得

对一个复杂的问题，从简单的开始，比如这道题，不妨从最简单的三个数字开始，三个数字才能存水，那么三个数字有几种组合呢？某种角度上可以分成四种【大，中，小】【小，中，大】【大，小，中】【中，小，大】。仔细想想，我们发现，只要最左边大于最右边，那么总有可能，就是总有可能当前最右边的柱子上边也能盛水。所以我们把【大，#，小】归为一种。对【小，中，大】，这个根本不可能盛水，直接更新左右指针。只剩下最后的【中，小，大】情况，这种情况自成一派，和后面的没关系，我们计算一下面积。

当然，上面是三个数，其实，中间有几个数不重要，可以把中间看成一个整体。