h989: Waimai 超人與 Hehe 遊俠 (Easy Version)
Tags : 數學
Accepted rate : 5人/5人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-06-19 19:04

Content

此題為這題的簡單版,差別在於無修改操作且只詢問所有區間一次。

$\text{Waimai}$ 超人與 $\text{Hehe}$ 遊俠組成的英雄團體「$\text{Waimaihehe}$」常常打擊罪犯,再壞的壞人,聽到「$\text{Waimaihehe}$」這個詞後都會嚇得聞風喪膽。

只是打擊罪犯雖然能獲得民眾的愛戴,但是卻不能賺錢,所以 $\text{Waimai}$ 超人與 $\text{Hehe}$ 遊俠必須要去打工。

今天他們的工作是當清潔工,他們的要做的就是刷馬桶,一共有 $n$ 個馬桶,有些馬桶是正在被刷的馬桶,其他人無法使用,而沒有被刷的馬桶就可以使用。$\text{Waimai}$ 超人與 $\text{Hehe}$ 遊俠觀察到一個有趣的現象,如果某個馬桶正在被刷,或是它相鄰的馬桶有人正在使用,那其他人就不會使用這個馬桶。

馬桶可能會被刷,就不能使用了。$\text{Waimai}$ 超人與 $\text{Hehe}$ 遊俠想要問你:今天所有 $n$ 個馬桶都開放使用,那最多有幾個馬桶可以同時被使用呢?

Input

第一行有一個正整數 $n$,代表有幾個馬桶。

第二行有 $n$ 個數字,代表由左到右第 $1\sim n$ 個馬桶的狀態,若狀態 $= 1$,代表此馬桶沒有被刷,可以使用,若狀態 $= 0$,代表此馬桶正在被刷,不能使用。

  • $1 \leq n \leq 10^5$
Output

輸出一個整數,代表所有馬桶都開放的話,最多可以有幾個人同時使用。

Sample Input #1
10
0 0 0 1 1 0 1 0 1 1
Sample Output #1
3
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (20%): 2.0s , <1M
不公開 測資點#1 (20%): 2.0s , <1M
不公開 測資點#2 (20%): 2.0s , <1M
不公開 測資點#3 (20%): 2.0s , <1M
不公開 測資點#4 (20%): 2.0s , <1M
Hint :

在範例中,可以使用第 $4, 7, 9$ 個馬桶。

---------------------------------------------------------------------

$100\%:無特別限制$

Tags:
數學
出處:
第六屆簡單的小競賽 [管理者: becaido(Caido) ]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」