码蹄集丨移水造海_2023码蹄集17次周赛

题目来源：码蹄集

题意如图：

根据输入，我们要求蓝色方块的个数，即最多能倒多少桶水不会溢出

算法思路：

从下往上填充：

遍历python给定数组的第二个元素到倒数第二个元素，如果这一元素加1后小于等于左方所有元素的最大值且小于等于右方所有元素的最大值，那么就可以给这个元素加1，并且count计数器加1，反之这个元素不加1，且count计数器也不加1，按此规则遍历完指定区间的元素后，返回count计数器的值

Python代码实现（会超时）：

n = int(input())
arr = list(map(int, input().split()))

def count_elements(arr):
    n = len(arr)
    count = 0
    for i in range(1, n-1):
        while arr[i] + 1 <= max(arr[0:i]) and arr[i] + 1 <= max(arr[i+1:n]):
            arr[i] += 1
            count += 1
    return count

print(count_elements(arr))
1
2
3
4
5
6
7
8
9
10
11
12
13

我感觉应该还有一种从上往下填充的思路，就是先找到最高层，然后找第二高层，从第二高层的位置往最高层所在位置划线，求第二高与最高层中间所有层的差值并求和，然后再找第三高层，到这我感觉接下来情况就有点复杂了，需要分情况讨论，不如从下往上填充起来简单，就没再想了。

但是上述代码只能通过3/10的测试用例，原因是超时了。

代码优化：

C++代码实现，原文链接，这个是可以通过码蹄集所有测试用例的：

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,maxn=0;
    cin>>n;
    vector<int>a;
    int tmp;
    int ans=0;
    for(int i=0;i<n;i++)
    {
       cin>>tmp;
       maxn=max(maxn,tmp);//获取最大高度
       a.push_back(tmp);
    }
   /*思路：从高度为1开始遍历到maxn，计算不低于每一层高度的坐标点之间的距离，则是可以加的水的桶数*/
    for(int i=1;i<=maxn;i++)//从高度为1开始遍历到maxn
    {
        int last=-1;
        for(int j=0;j<n;j++)
        {
            if(a[j]>=i)
            {
                 if(last!=-1) ans+=j-last-1;
                 last=j;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

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

Python优化代码（优化了，但不多，因为算法本质没变）：

n = int(input())
arr = list(map(int, input().split()))

def count_elements(arr):
    n = len(arr)
    count = 0
    for i in range(1, n-1):
        max_left = max(arr[0:i])
        max_right = max(arr[i+1:n])
        next_val = arr[i] + 1

        while next_val <= max_left and next_val <= max_right:
            next_val += 1
            count += 1
    print(count)

count_elements(arr)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

这次可以通过4个测试用例了，也算进步了吧，没精力了，就这样吧。