b297: 啊!殭屍
Tags :
Accepted rate : 55人/77人 ( 71% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-09-24 11:37

Content
有N隻殭屍(A1~AN)排成一排向你撲過來,殭屍有兩種,一種跑比較快,一種跑比較慢。你身上有一把藥物注射槍,它可以讓某個殭屍的類型改變(快轉慢或是慢轉快)。你還有一把藥物噴射槍,可以讓某個殭屍和在他前面的所有殭屍的類型都改變,比如你對Ai殭屍發射,Ai,Ai-1,Ai-2,...,A1的型態都會改變。你要把所有殭屍變成慢速殭屍,你希望你藥物注射槍和藥物噴射槍發使用次數的總和越小越好,請問你最少要發射幾次呢?
Input
第一行有一個數字N代表殭屍的數量(N<=10000000),第二行有長度為N的0/1字串,其中第i個字元是1就代表Ai是慢速殭屍,第i個字元是0就代表Ai是快速的殭屍。
Output
一個數字,代表最少共要發射多少次。
 
 
對於#Sample 1,你最好的方式是對著A5發射藥物噴射槍,然後再對A3發射藥物注射槍。 
對於#Sample 3,你什麼都不用做。 
Sample Input
#Sample Input 1
5
00100

#Sample Input 2
8
10001101

#Sample Input 3
10
1111111111
Sample Output
#Sample Output 1
2

#Sample Output 2
3

#Sample Output 3
0
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (25%): 3.0s , <1K
公開 測資點#1 (25%): 3.0s , <1K
公開 測資點#2 (25%): 3.0s , <1M
公開 測資點#3 (25%): 3.0s , <10M
Hint :
Tags:
出處:
103學年度板橋高中校內資訊學科能力競賽(一)抄襲自 step5-0004 [管理者:
snail (蝸牛)
]


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