題目1 回文數組

小藍在無聊時隨機生成了一個長度為 n 的整數數組，數組中的第 i 個數為 ai，他覺得隨機生成的數組不太美觀，想把它變成回文數組，也是就對于任意 i∈[1,n] 滿足 $a_i=a_{n?i}+1$。

小藍一次操作可以指定相鄰的兩個數，將它們一起加 1 或減 1；也可以只指定一個數加 1 或減 1，請問他最少需要操作多少次能把這個數組變成回文數組？

輸入格式

輸入的第一行包含一個正整數 n。

第二行包含 n 個整數 a1,a2,…,an，相鄰整數之間使用一個空格分隔。

輸出格式

輸出一行包含一個整數表示答案。

數據范圍

對于 20% 的評測用例，1≤n≤10。
對于所有評測用例，$1\le n\le 10^5，?10^6\le a_i\le 10^6$。

輸入樣例：

4
1 2 3 4

輸出樣例：

3

樣例解釋

第一次操作將 a1,a2 加 1，變為 2,3,3,4;

后面兩次操作將 a1 加 1，變為 4,3,3,4。

---

思路

1. +1的操作等價于-1，例如：1 2 3 4 ??1 2 2 1 or 1 2 3 4 ??4 3 3 4
2. 那么我們只選擇一種操作，-1
3. 從兩邊分別統計差值，比如對于樣例，0 0 1 2
4. 遍歷，進行-1操作，對于連續的兩個位置-1，當做一次操作，最終結果為0 0 0 1
5. 遍歷最終位置為倒數第二個元素，此時如果倒數第一個元素不為0，單獨進行-1操作

python代碼

import os
import sys
n=int(input())
data=list(map(int,input().split()))
a=[0]*(n)
ans=0
l,r=0,n-1
while l<=n//2 and r>=n//2:t=min(data[l],data[r])data[l]-=tif l!=r:data[r]-=tl+=1r-=1
for i in range(n-1):t=data[i]if t>0:ans+=tdata[i+1]-=min(t,data[i+1])
if data[n-1]>0:ans+=data[n-1]
print(ans)

知識點

藍橋杯筆記：藍橋杯備賽筆記

1. 思維？貪心？回文數？