思路：模拟

其实就是求-1左边和右边的最小值，然后累加起来即为答案。

时间复杂度

$O(n)$

c++代码

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin>>n;
    vector<int>vec(2, INT_MAX);
    int x;
    int index = 0;
    for(int i = 0; i < n; i++){
        cin>>x;
        if(x == -1) {
            index++;
        }else {
            vec[index] = min(vec[index], x);
        }
    }
    cout<<vec[0] + vec[1];
    return 0;
}

python代码

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

lmin = 0

pos = 0
for i in range(n):
    if a[i] == -1:
        pos = i
        break

print(min(a[:pos]) + min(a[pos+1:]))

Java代码

import java.util.*;

class Main {
    public static void main(String[]args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a  = new int[n];
        for (int i = 0 ; i < n ; i++) a[i] = sc.nextInt();

        for (int i = 0 ; i < n ; i++) {
            if (a[i] == -1) {
                int p1 = i-1, p2 = i+1;
                int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
                while (p1 >= 0) {
                    min1 = Math.min(min1, a[p1--]);
                }
                while (p2 < n) {
                    min2 = Math.min(min2, a[p2++]);
                }
                System.out.println(min1 + min2);
                return;
            }
        }

    }
}

题目描述

现在有一个警察抓小偷的游戏，小红刚好玩到让小偷跑到了一个长长的桥面上去。

假设在桥面上，有$N$块紧密相连的桥板。标号1~$N$，小偷已经逃到了标号为$K$的桥板上。现在， 小红可以用超能力拆除一些桥板来使得小偷掉落河中，然而他无法拆除小偷所踩的桥板$K$。每个桥板拆除时都需要支付不同的代价$Aᵢ$，当桥体两侧的桥板都没有与河两岸连接时，则桥和小偷会一起掉落到河中。

求小红需要支付的最小代价。

假设某一情况如图：

桥体1和桥体4可以通过分别支付8和3的代价来拆除，此时小偷所在的桥板2和桥板3一起掉落河中。因此最小代价为11.

输入描述

第一行给出$N$， 表示冰块的数量。 第二行中，按顺序给出代表打破第i块冰块所需的力的$Aᵢ$。 题目保证企鹅所在的地方用$-1$表示， 没有企鹅位于冰块$1$或冰块$N$的情况。 $3≤N≤2*10⁵,1≤Aᵢ≤10⁹$

输出描述

输出可以将企鹅击落到水中的最小力。

示例1

输入

5
8 -1 7 3 6

输出

11

说明

见题目举例

示例2

输入

10
49 46 -1 55 54 53 52 51 50 51

输出

96

说明 打破桥面2和桥面9， 最小代价为46+50=96