---
title: "Codeforces Round 786 (Div. 3) E(枚舉+數論)"
tags: 題解, 枚舉, 數論
---

https://codeforces.com/contest/1674/problem/E

#### 題意

有一個長度 $N$、正整數的數組 $A$，每次操作可以選擇一個位置 $i$，將 $A[i]$ 扣掉 $2$ 且 $A[i-1]$、$A[i+1]$ 若存在的話各自可以扣掉 $1$。元素被扣到零後如果再被扣則會保持為零，且已經是零的元素仍然可以被選擇。

求最少要幾次操作可以將數組中至少兩個元素都扣到零。

#### 思路

觀察發現這兩個被扣到零的元素，其位置關係有三種可能：
1. 距離 $>=3$
2. 距離 $=2$，即間隔一個元素
3. 距離 $=1$，即它們兩個是相鄰的

方案一的答案就是兩個最小元素各自扣到零所需的操作。

方案二可以先選中間位置操作，直到較小的變成零，剩餘較大的那個可以用扣 $2$ 的操作。

方案三則是每次選兩個中較大的那個，直到兩者都變成零。簡單來說就是先選擇大的那個，直到兩者變成一樣；接下來輪流選擇它們，每次會扣掉 $2+1=3$，直到扣完即可。

#### Code

def solve():
    N = int(input())
    A = list(map(int, input().split()))

    mn = min(A)
    mn_i = A.index(mn)
    A[mn_i] = INF
    mn2 = min(A)
    A[mn_i] = mn

    ans = (mn + 1) // 2 + (mn2 + 1) // 2

    for i in range(1, N - 1):
        mn, mx = min(A[i - 1], A[i + 1]), max(A[i - 1], A[i + 1])
        ans = min(ans, mn + (mx - mn + 1) // 2)

    for i in range(N - 1):
        mn, mx = min(A[i], A[i + 1]), max(A[i], A[i + 1])

        diff = mx - mn
        if mn >= diff:
            cur = diff
            mx -= 2 * diff
            mn -= diff
            cur += (mn + mx + 2) // 3
        else:
            cur = mn
            mx -= 2 * mn
            mn -= mn
            cur += (mx + 1) // 2

        ans = min(ans, cur)

    print(ans)

if __name__ == "__main__":
    solve()